Approximating Knapsack and Partition via Dense Subset Sums

Mingyang Deng, Ce Jin, Xiao Mao

Knapsack and Partition are two important additive problems whose fine-grained complexities in the $(1-\epsilon )$-approximation setting are not yet settled. In this work, we make…