9 papers
Continuous Defensive Domination Problems
Christoph Grüne, Tom JanÃen
The problem Defensive -Covering, for some covering range , is a continuous facility location problem on undirected graphs where all edges have unit length. It is a gener…
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…
Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
Christoph Grüne, Lasse Wulf
In bilevel and robust optimization we are concerned with combinatorial min-max problems, for example from the areas of min-max regret robust optimization, network interdiction, mos…
The Complexity Classes of Hamming Distance Recoverable Robust Problems
Christoph Grüne
In the well-known complexity class NP are combinatorial problems, whose optimization counterparts are important for many practical settings. These problems typically consider full…
The Complexity of Stackelberg Pricing Games
Christoph Grüne, Dorothee Henke, Eva Rotenberg +1
We consider Stackelberg pricing games, which are also known as bilevel pricing problems, or combinatorial price-setting problems. This family of problems consists of games between…
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…