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

David J. Rader Jr, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

37 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)159-166
JournalOperations research letters
Issue number3
Publication statusPublished - 2002


  • IR-74848
  • Approximation scheme
  • Knapsack problem
  • Computational Complexity
  • Dynamic Programming
  • Approximability
  • METIS-208616


Dive into the research topics of 'The quadratic 0-1 knapsack problem with series-parallel support'. Together they form a unique fingerprint.

Cite this