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


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
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
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:
Official URL:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 208616