Hardness of Approximation for Knapsack Problems

• Tipo: Artigo em Revista Científica Internacional
• Data: 2015

Autores

Buhrman, H (Autor) Outra; Loff, B (Autor) Outra; Torenvliet, L (Autor) Outra

Revista

Título: Theory of Computing Systems

Vol. 56

Páginas: 372-393

ISSN: 1432-4350

Editora: Springer Nature

Indexação

Scopus - 5 Citações

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica