Final published version
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
| Publication date | 2014 |
|---|---|
| Host publication | Theory and Applications of Models of Computation. TAMC 2014 |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 203-215 |
| Number of pages | 13 |
| ISBN (print) | 9783319060880 |
| <mark>Original language</mark> | English |
| Event | 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014 - Chennai, India Duration: 11/04/2014 → 13/04/2014 |
| Conference | 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014 |
|---|---|
| Country/Territory | India |
| City | Chennai |
| Period | 11/04/14 → 13/04/14 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Publisher | Springer |
| Volume | 8402 |
| ISSN (Print) | 0302-9743 |
| ISSN (electronic) | 1611-3349 |
| Conference | 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014 |
|---|---|
| Country/Territory | India |
| City | Chennai |
| Period | 11/04/14 → 13/04/14 |
We consider the weight-reducible knapsack problem, where we are given a limited budget that can be used to decrease item weights, and we would like to optimize the knapsack objective value using such weight improvements. We develop a pseudo-polynomial algorithm for the problem, as well as a polynomial-time 3-approximation algorithm based on solving the LP-relaxation. Furthermore, we consider the special case of one degree of improvement with equal improvement costs for each item, and present a linear-time 3-approximation algorithm based on solving a cardinality-constrained and a classic knapsack problem, and show that the analysis of the polynomial-time 3-approximation algorithm can be improved to yield a 2-approximation.