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

David J. Rader Jr; Gerhard Woeginger

doi:10.1016/S0167-6377(02)00122-0

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

David J. Rader Jr, Gerhard Woeginger

Discrete Mathematics and Mathematical Programming

Research output: Contribution to journal › Article › Academic › peer-review

42 Citations (Scopus)

10 Downloads (Pure)

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 language	English
Pages (from-to)	159-166
Journal	Operations research letters
Volume	30
Issue number	3
DOIs	https://doi.org/10.1016/S0167-6377(02)00122-0
Publication status	Published - 2002

Keywords

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

Access to Document

10.1016/S0167-6377(02)00122-0

Cite this

@article{04e6318f08984ba7805eb84aa7210989,

title = "The quadratic 0-1 knapsack problem with series-parallel support",

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.",

keywords = "IR-74848, Approximation scheme, Knapsack problem, Computational Complexity, Dynamic Programming, Approximability, METIS-208616",

author = "{Rader Jr}, {David J.} and Gerhard Woeginger",

year = "2002",

doi = "10.1016/S0167-6377(02)00122-0",

language = "English",

volume = "30",

pages = "159--166",

journal = "Operations research letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

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

AU - Rader Jr, David J.

AU - Woeginger, Gerhard

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - IR-74848

KW - Approximation scheme

KW - Knapsack problem

KW - Computational Complexity

KW - Dynamic Programming

KW - Approximability

KW - METIS-208616

U2 - 10.1016/S0167-6377(02)00122-0

DO - 10.1016/S0167-6377(02)00122-0

M3 - Article

SN - 0167-6377

VL - 30

SP - 159

EP - 166

JO - Operations research letters

JF - Operations research letters

IS - 3

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this