Article ID Journal Published Year Pages File Type
1141546 Discrete Optimization 2010 6 Pages PDF
Abstract

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

Keywords
Related Topics
Physical Sciences and Engineering Mathematics Control and Optimization
Preview
Pinpointing the complexity of the interval min–max regret knapsack problem
Authors
, ,