Header menu link for other important links
Approximation algorithms for the weight-reducible knapsack problem
M. Goerigk, Y. Sabharwal, A. Schöbel,
Published in Springer Verlag
Volume: 8402 LNCS
Pages: 203 - 215
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. © 2014 Springer International Publishing Switzerland.
About the journal
Published in Springer Verlag
Open Access
Impact factor