Lin Chen

collaborators

4 papers

math.OC2025

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 $n^{O (m)} (m \cdot max {Δ, ∥ b ∥_{\infty}})^{O (m^{2})}$ , where $m$ is the number of constraints, $n…

cs.DS2025

Weakly Approximating Knapsack in Subquadratic Time

Lin Chen, Jiayi Lian, Yuchen Mao +1

We consider the classic Knapsack problem. Let $t$ and $OPT$ be the capacity and the optimal value, respectively. If one seeks a solution with total profit at least $\mathr…

cs.DS2025

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…

cs.DS2025

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 $O (n + 1/ ε)$ -time. This is the b…