The quadratic 0–1 knapsack problem with series–parallel support

Share/Save/Bookmark

Rader Jr, David J. and Woeginger, Gerhard J. (2002) The quadratic 0–1 knapsack problem with series–parallel support. Operations Research Letters, 30 (3). pp. 159-166. ISSN 0167-6377

[img]PDF
Restricted to UT campus only
: Request a copy
128Kb
Abstract:We consider various special cases of the quadratic 0–1 knapsack problem (QKP) for which the underlying graph structure is fairly simple. For the variant with edge series–parallel graphs, we give a dynamic programming algorithm with pseudo-polynomial time complexity, and a fully polynomial time approximation scheme. In strong contrast to this, the variant with vertex series–parallel graphs is shown to be strongly NP-complete.
Item Type:Article
Copyright:© 2002 Elsevier
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74848
Official URL:http://dx.doi.org/10.1016/S0167-6377(02)00122-0
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 208616