Standard
Approximation algorithms for the weight-reducible knapsack problem. /
Goerigk, Marc; Sabharwal, Yogish; Schöbel, Anita et al.
Theory and Applications of Models of Computation. TAMC 2014. Berlin: Springer, 2014. p. 203-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8402 ).
Research output: Contribution in Book/Report/Proceedings - With ISBN/ISSN › Conference contribution/Paper › peer-review
Harvard
Goerigk, M, Sabharwal, Y, Schöbel, A & Sen, S 2014,
Approximation algorithms for the weight-reducible knapsack problem. in
Theory and Applications of Models of Computation. TAMC 2014. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8402 , Springer, Berlin, pp. 203-215, 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014, Chennai, India,
11/04/14.
https://doi.org/10.1007/978-3-319-06089-7-14
APA
Vancouver
Goerigk M, Sabharwal Y, Schöbel A, Sen S.
Approximation algorithms for the weight-reducible knapsack problem. In Theory and Applications of Models of Computation. TAMC 2014. Berlin: Springer. 2014. p. 203-215. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-06089-7-14
Author
Bibtex
@inproceedings{54a3367250594c928ba98d2e091fe4d2,
title = "Approximation algorithms for the weight-reducible knapsack problem",
abstract = "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. ",
keywords = "approximation algorithms, improvable optimization problems, knapsack problem",
author = "Marc Goerigk and Yogish Sabharwal and Anita Sch{\"o}bel and Sandeep Sen",
year = "2014",
doi = "10.1007/978-3-319-06089-7-14",
language = "English",
isbn = "9783319060880",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "203--215",
booktitle = "Theory and Applications of Models of Computation. TAMC 2014",
note = "11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014 ; Conference date: 11-04-2014 Through 13-04-2014",
}
RIS
TY - GEN
T1 - Approximation algorithms for the weight-reducible knapsack problem
AU - Goerigk, Marc
AU - Sabharwal, Yogish
AU - Schöbel, Anita
AU - Sen, Sandeep
PY - 2014
Y1 - 2014
N2 - 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.
AB - 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.
KW - approximation algorithms
KW - improvable optimization problems
KW - knapsack problem
U2 - 10.1007/978-3-319-06089-7-14
DO - 10.1007/978-3-319-06089-7-14
M3 - Conference contribution/Paper
SN - 9783319060880
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 203
EP - 215
BT - Theory and Applications of Models of Computation. TAMC 2014
PB - Springer
CY - Berlin
T2 - 11th Annual Conference on Theory and Applications of Models of Computation, TAMC 2014
Y2 - 11 April 2014 through 13 April 2014
ER -
