Pinpointing the complexity of the interval min-max regret knapsack problem

V.G. Deineko; G.J. Woeginger

doi:10.1016/j.disopt.2010.03.008

Pinpointing the complexity of the interval min-max regret knapsack problem

V.G. Deineko, G.J. Woeginger

Combinatorial Optimization 1

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

14 Citations (Scopus)

Abstract

We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.

Original language	English
Pages (from-to)	191-196
Journal	Discrete Optimization
Volume	7
Issue number	4
DOIs	https://doi.org/10.1016/j.disopt.2010.03.008
Publication status	Published - 2010

Access to Document

10.1016/j.disopt.2010.03.008

Cite this

@article{040bccba420f4b4788d55c389aa60358,

title = "Pinpointing the complexity of the interval min-max regret knapsack problem",

abstract = "We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.",

author = "V.G. Deineko and G.J. Woeginger",

year = "2010",

doi = "10.1016/j.disopt.2010.03.008",

language = "English",

volume = "7",

pages = "191--196",

journal = "Discrete Optimization",

issn = "1572-5286",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

T1 - Pinpointing the complexity of the interval min-max regret knapsack problem

AU - Deineko, V.G.

AU - Woeginger, G.J.

PY - 2010

Y1 - 2010

N2 - We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.

AB - We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy.

U2 - 10.1016/j.disopt.2010.03.008

DO - 10.1016/j.disopt.2010.03.008

M3 - Article

SN - 1572-5286

VL - 7

SP - 191

EP - 196

JO - Discrete Optimization

JF - Discrete Optimization

IS - 4

ER -

Pinpointing the complexity of the interval min-max regret knapsack problem

Abstract

Access to Document

Fingerprint

Cite this