|
|||||
|
|
Pinpointing the complexity of the interval min–max regret knapsack problem |
|
| Authors: | Vladimir G Deineko Gerhard J Woeginger |
| Institution: | a Warwick Business School, The University of Warwick, Coventry CV4 7AL, United Kingdom;b Department of Mathematics and Computer Science, TU Eindhoven, P.O. Box 513, 5600 MB Eindhoven, Netherlands |
| Abstract: | We show that a natural robust optimization variant of the knapsack problem is complete for the second level of the polynomial hierarchy. |
| Keywords: | Robust optimization Computational complexity Polynomial hierarchy |
| 本文献已被 ScienceDirect 等数据库收录！ | |