Home > Research > Publications & Outputs > Improvable Knapsack Problems

Research

Associated organisational unit

Links

View graph of relations

Improvable Knapsack Problems

Research output: Working paper

Published

Standard

Improvable Knapsack Problems. / Goerigk, Marc; Sabharwal, Yogish; Schöbel, Anita et al.
2016.

Research output: Working paper

Harvard

Goerigk, M, Sabharwal, Y, Schöbel, A & Sen, S 2016 'Improvable Knapsack Problems'. <https://arxiv.org/abs/1607.08338>

APA

Goerigk, M., Sabharwal, Y., Schöbel, A., & Sen, S. (2016). Improvable Knapsack Problems. https://arxiv.org/abs/1607.08338

Vancouver

Goerigk M, Sabharwal Y, Schöbel A, Sen S. Improvable Knapsack Problems. 2016 Jul 28.

Author

Goerigk, Marc ; Sabharwal, Yogish ; Schöbel, Anita et al. / Improvable Knapsack Problems. 2016.

Bibtex

@techreport{d4430cd0097c4e3db67580c520ef94f8,
title = "Improvable Knapsack Problems",
abstract = "We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Which items should be improved to which degree such that the resulting classic knapsack problem yields maximum profit? We present a detailed analysis for several cases of improvable knapsack problems, presenting constant factor approximation algorithms and two PTAS.",
author = "Marc Goerigk and Yogish Sabharwal and Anita Sch{\"o}bel and Sandeep Sen",
year = "2016",
month = jul,
day = "28",
language = "English",
type = "WorkingPaper",

}

RIS

TY - UNPB

T1 - Improvable Knapsack Problems

AU - Goerigk, Marc

AU - Sabharwal, Yogish

AU - Schöbel, Anita

AU - Sen, Sandeep

PY - 2016/7/28

Y1 - 2016/7/28

N2 - We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Which items should be improved to which degree such that the resulting classic knapsack problem yields maximum profit? We present a detailed analysis for several cases of improvable knapsack problems, presenting constant factor approximation algorithms and two PTAS.

AB - We consider a variant of the knapsack problem, where items are available with different possible weights. Using a separate budget for these item improvements, the question is: Which items should be improved to which degree such that the resulting classic knapsack problem yields maximum profit? We present a detailed analysis for several cases of improvable knapsack problems, presenting constant factor approximation algorithms and two PTAS.

M3 - Working paper

BT - Improvable Knapsack Problems

ER -