Showing 2025Show all
3 papers · 1 filter
cs.DS2025
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…
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
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…