Hardness of Approximation for Knapsack Problems

• Type: Article in International Scientific Journal
• Date: 2015

Authors

Buhrman, H (Author) Other; Loff, B (Author) Other; Torenvliet, L (Author) Other

Journal

Title: Theory of Computing Systems

Vol. 56

Pages: 372-393

ISSN: 1432-4350

Publisher: Springer Nature

Indexing

Scopus - 5 Citations

Other information

Authenticus ID: P-00N-9SV

DOI: 10.1007/s00224-014-9550-z

Abstract (EN): We show various hardness results for knapsack and related problems; in particular we will show that unless the Exponential-Time Hypothesis is false, subset-sum cannot be approximated any better than with an FPTAS. We also provide new unconditional lower bounds for approximating knapsack in Ketan Mulmuley¿s parallel PRAM model. Furthermore, we 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. © 2014, Springer Science+Business Media New York.

Language: English

Type (Professor's evaluation): Scientific