Approximation algorithms and hardness of approximation for knapsack problems
Harry Buhrman, Bruno Serra S. Loff Barreto, Leen Torenvliet · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2012
We show various hardness of approximation algorithms for knapsack and related problems; in particular we will show that unless the Exponential-Time Hypothesis is false, then subset-sum cannot be approximated any better than with an FPTAS. We also give a simple new algorithm for approximating knapsack and subset-sum, that can be adapted to work for small space, or in small parallel time. Finally, we prove that knapsack can not be solved in Mulmuley's parallel PRAM model, even when the input is restricted to small bit-length.