h1

TY  - THES
AU  - Grüne, Christoph Manfred
TI  - Computational complexity of problems in robust, bilevel and online optimization
PB  - RWTH Aachen University
VL  - Dissertation
CY  - Aachen
M1  - RWTH-2025-09741
SP  - 1 Online-Ressource : Illustrationen
PY  - 2025
N1  - Veröffentlicht auf dem Publikationsserver der RWTH Aachen University
N1  - Dissertation, RWTH Aachen University, 2025
AB  - This thesis deals with the complexity of robust, bilevel, and online optimization. In these areas, we are concerned with min-max (respectively multi-stage) problems from the popular areas of network interdiction, most vital vertex problems, min-max regret optimization, two-stage adjustable problems, recoverable robustness, and online optimization. Although these areas have been well-researched for more than two decades, and one would naturally expect most of the problems to be complete for lower levels of the polynomial hierarchy or polynomial space, almost no hardness results are known. We address this issue by designing two reduction frameworks with the goal of analyzing the common substructure of combinatorial problems that include some form of uncertainty, which induces similar complexity behavior. The reduction frameworks work as follows. We first provide a general definition of a combinatorial problem, which is also called the nominal problem. Based on this definition of a nominal problem, we are able to derive definitions for more general variations of that problem that additionally model some kind of uncertainty. The general idea is now to examine the reductions between the nominal problems and determine if additional properties hold that help us to directly derive reductions for the more general variations. Accordingly, we provide a definition of such a reduction and show that these properties are already fulfilled by existing reductions or slight modifications of them. We apply these frameworks to nominal problems that are <span style="font-family:helvetica">NP-complete and derive complexity results for completeness in the polynomial hierarchy and in <span style="font-family:helvetica">PSPACE.The first framework is concerned with subset search problems (or in short SSP), thus it is named SSP framework. A subset search problem is a combinatorial problem that consists of instances <i>I</i> that contain a universe <i>U</i> together with additional information. A solution S  ∈ <i>S</i> is a subset of the universe, i.e. S  ⊆ <i>U</i>.The corresponding SSP reductions are usual reductions with an additional injective function that maps the universe of the one problem into that of the other. Indeed, many existing reductions on the <span style="font-family:helvetica">NP-level fulfill this SSP property. Based on this notion, we are able to üpgrade" the SSP reductions between the nominal problems to reductions between the problem versions in the areas of robust and bilevel optimization. Concretely, we apply this framework to the areas of interdiction, min-max regret optimization, two-stage adjustable robustness, and recoverable robustness, and prove Σ<sup>p</sup><sub>2</sub>- and Σ<sup>p</sup><sub>3</sub>-completeness for the corresponding problems if the nominal problem is <span style="font-family:helvetica">NP-complete. The second framework considers combinatorial problems, which can be described by an underlying universe U and nested relations R over the universe. The corresponding reduction is termed universe gadget reduction. The special property of a universe gadget reduction from problem A to B is that a gadget is created for every universe element and every relational element from any of the relations of problem A. These gadgets consist of the universe and relation elements of the problem B and are disjoint. Based on this reduction, we are able to show Σ<sup>p</sup><sub>3</sub>-completeness for variations of recoverable robust problems and <span style="font-family:helvetica">PSPACE-completeness for several online graph problems with a map.
LB  - PUB:(DE-HGF)11
DO  - DOI:10.18154/RWTH-2025-09741
UR  - https://publications.rwth-aachen.de/record/1021909
ER  -