4 papers
Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
Christoph Grüne, Berit Johannes, James B. Orlin +1
Many natural optimization problems derived from admit bilevel and multilevel extensions in which decisions are made sequentially by multiple players with conflicting objec…
A Compendium of Reductions: reductions.network
Christoph Grüne, Femke Pfaue
The website reductions.network serves as a comprehensive database for exploring problems and reductions between them. It presents several complexity classes in the form of an inter…
The Complexity of Blocking All Solutions
Christoph Grüne, Lasse Wulf
We consider the general problem of blocking all solutions of some given combinatorial problem with only few elements. For example, the problem of destroying all maximum cliques of…
On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
Christoph Grüne, Lasse Wulf
Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consid…