Knapsack with variable weights satisfying linear constraints

Kameng Nip (), Zhenbo Wang () and Zizhuo Wang ()
Additional contact information
Kameng Nip: Tsinghua University
Zhenbo Wang: Tsinghua University
Zizhuo Wang: University of Minnesota

Journal of Global Optimization, 2017, vol. 69, issue 3, No 9, 713-725

Abstract: Abstract We introduce a variant of the knapsack problem, in which the weights of items are also variables but must satisfy a system of linear constraints, and the capacity of knapsack is given and known. We discuss two models: (1) the value of each item is given; (2) the value-to-weight ratio of each item is given. The goal is to determine the weight of each item, and to find a subset of items such that the total weight is no more than the capacity and the total value is maximized. We provide several practical application scenarios that motivate our study, and then investigate the computational complexity and corresponding algorithms. In particular, we show that if the number of constraints is a fixed constant, then both problems can be solved in polynomial time. If the number of constraints is an input, then we show that the first problem is NP-Hard and cannot be approximated within any constant factor unless $$\mathrm{P}= \mathrm{NP}$$ P = NP , while the second problem is NP-Hard but admits a polynomial time approximation scheme. We further propose approximation algorithms for both problems, and extend the results to multiple knapsack cases with a fixed number of knapsacks and identical capacities.

Keywords: Knapsack; Linear programming; Computational complexity; Approximation algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-017-0540-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:69:y:2017:i:3:d:10.1007_s10898-017-0540-y

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-017-0540-y

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().