Approximating Knapsack and Partition via Dense Subset Sums
Mingyang Deng, Ce Jin, Xiao Mao
Abstract
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.
Topics & Concepts
Knapsack problemPartition (number theory)CombinatoricsMathematicsUpper and lower boundsContext (archaeology)Exponential functionDiscrete mathematicsAlgorithmMathematical analysisPaleontologyBiologyComplexity and Algorithms in GraphsOptimization and Search ProblemsComputational Geometry and Mesh Generation