6 papers
Dense Subset Sum in Multi-Dimension
Lin Chen, Tingwei Hu, Yuchen Mao +1
The paper studies the structure of subset sums of many vectors in a multi‑dimensional integer grid, showing that when the set is sufficiently dense it contains large generalized pr…
An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, Yuchen Mao +1
We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set of positive integers and a target , Subset Sum asks whether some subset of sums to…
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, $…
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…
A Note on Deterministic FPTAS for Partition
Lin Chen, Jiayi Lian, Yuchen Mao +1
We consider the Partition problem and propose a deterministic FPTAS (Fully Polynomial-Time Approximation Scheme) that runs in -time. This is the b…