22 citations · 52 across the 22 of their papers we have counts for
25 papers
Dense Subset Sum in Multi-Dimension
Lin Chen, Tingwei Hu, Yuchen Mao +1
We study the additive structure of dense subset sum in multi-dimension, and use the structure to develop efficient algorithms for the dense subset sum problem. More precisely, give…
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…
Approximation algorithms for integer programming with resource augmentation
Hauke Brinkop, Hua Chen, Lin Chen +2
The classic algorithm [Papadimitriou, J.ACM '81] for IPs has a running time , where is the number of constraints, $n…
Weakly Approximating Knapsack in Subquadratic Time
Lin Chen, Jiayi Lian, Yuchen Mao +1
We consider the classic Knapsack problem. Let and be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathr…
Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
Lin Chen, Yuchen Mao, Guochuan Zhang
Existence of long arithmetic progression in sumsets and subset sums has been studied extensively in the field of additive combinatorics. These additive combinatorics results play a…
Approximating Partition in Deterministic Near-Linear Time
Lin Chen, Jiayi Lian, Yuchen Mao +1
We propose a deterministic -time FPTAS (Fully Polynomial-Time Approximation Scheme) for the classical Partition problem. This is the best possible (up…