3645. A large and natural Class of Sigma-2- and Sigma-3-complete Problems in Bilevel and Robust Optimization
Invited abstract in session TD-4: Robust and Multi-Level Optimization, stream MINLP.
Tuesday, 14:30-16:00Room: 1001 (building: 202)
Authors (first author is the speaker)
| 1. | Lasse Wulf
|
| Institute of discrete mathematics, TU Graz |
Abstract
Because Sigma-2- and Sigma-3-hardness proofs are usually tedious and difficult, not so many complete problems for these classes are known. This is especially true in the areas of robust and bilevel optimization (we focus in this talk on min-max-regret, interdiction, most vital vertex, and two-stage robust optimization problems). Even though these areas are well-researched for over two decades and one would naturally expect many (if not most) of the problems occurring in these areas to be complete for the above classes, almost no completeness results exist in the literature. We address this lack of knowledge by introducing over 70 new Sigma-2-complete and Sigma-3-complete problems. We achieve this result by proving a new meta-theorem. This meta-theorem applies to most classical problems, like clique, vertex cover, knapsack, TSP, facility location and many more. In summary, our work reveals the interesting insight that a large amount of NP-complete problems have the property that their min-max versions are 'automatically' Sigma-2-complete.
Keywords
- Complexity and Approximation
- Robust Optimization
- Combinatorial Optimization
Status: accepted
Back to the list of papers