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

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:	Discrete Mathematics and Mathematical Programming (DMMP)
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

Show download statistics for this publication

Repository Staff Only: item control page

Metis ID: 208616