Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, Xiao Mao · Society for Industrial and Applied Mathematics eBooks · 2023
Knapsack and Partition are two important additive problems whose fine-grained complexities in the (1 — ε)-approximation setting are not yet settled. In this work, we make progress on both problems by giving improved algorithms.