Hardness of approximation for Knapsack problems
| Authors |
|
|---|---|
| Publication date | 2015 |
| Journal | Theory of Computing Systems |
| Volume | Issue number | 56 | 2 |
| Pages (from-to) | 372-393 |
| Number of pages | 21 |
| Organisations |
|
| Abstract | 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. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.1007/s00224-014-9550-z |
| Downloads |
10.1007_s00224-014-9550-z
(Final published version)
|
| Permalink to this page | |