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

David J. Rader Jr, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

35 Citations (Scopus)

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

Keywords

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

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

Cite this