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

V.G. Deineko, G.J. Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

8 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 languageEnglish
Pages (from-to)191-196
JournalDiscrete Optimization
Volume7
Issue number4
DOIs
Publication statusPublished - 2010

Fingerprint Dive into the research topics of 'Pinpointing the complexity of the interval min-max regret knapsack problem'. Together they form a unique fingerprint.

Cite this