22 citations · 43 across the 15 of their papers we have counts for
17 papers
Near-Tight Approximation Algorithms for Bottleneck Multiple Knapsack Problems
Lin Chen, Tingwei Hu, Yuchen Mao +5
In the bottleneck multiple knapsack problem, we are given a set of items and a set of knapsacks, where each item has a profit and a weight, and each knapsack has a capacity. Our go…
A Nearly Quadratic-Time FPTAS for Knapsack
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate the classic Knapsack problem and propose a fully polynomial-time approximation scheme (FPTAS) that runs in time. This improves…
Faster Algorithms for Bounded Knapsack and Bounded Subset Sum Via Fine-Grained Proximity Results
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate pseudopolynomial-time algorithms for Bounded Knapsack and Bounded Subset Sum. Recent years have seen a growing interest in settling their fine-grained complexity wit…
Improved Approximation Schemes for (Un-)Bounded Subset-Sum and Partition
Xiaoyu Wu, Lin Chen
We consider the SUBSET SUM problem and its important variants in this paper. In the SUBSET SUM problem, a (multi-)set of positive numbers and a target number are given,…
Approximation Algorithms for Interdiction Problem with Packing Constraints
Lin Chen, Xiaoyu Wu, Guochuan Zhang
We study a bilevel optimization problem which is a zero-sum Stackelberg game. In this problem, there are two players, a leader and a follower, who pick items from a common set. Bot…
FPT Algorithms for a Special Block-structured Integer Program with Applications in Scheduling
Hua Chen, Lin Chen, Guochuan Zhang
We consider integer programs whose constraint matrix has a special block structure: , where the objective function $…