% IMPORTANT: The following is UTF-8 encoded. This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.
@PHDTHESIS{Grne:1021909,
author = {Grüne, Christoph Manfred},
othercontributors = {Rossmanith, Peter and Goerigk, Marc},
title = {{C}omputational complexity of problems in robust, bilevel
and online optimization},
school = {RWTH Aachen University},
type = {Dissertation},
address = {Aachen},
publisher = {RWTH Aachen University},
reportid = {RWTH-2025-09741},
pages = {1 Online-Ressource : Illustrationen},
year = {2025},
note = {Veröffentlicht auf dem Publikationsserver der RWTH Aachen
University; Dissertation, RWTH Aachen University, 2025},
abstract = {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
$\mathsf{NP}$-complete and derive complexity results for
completeness in the polynomial hierarchy and in
$\mathsf{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 $\mathcal{I}$ that
contain a universe $\mathcal{U}$ together with additional
information. A solution $S \in \mathcal{S}$ is a subset of
the universe, i.e. $S \subseteq \mathcal{U}$.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 $\mathsf{NP}$-level fulfill this SSP
property. Based on this notion, we are able to "upgrade" 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 $\Sigma^p_2$- and $\Sigma^p_3$-completeness for
the corresponding problems if the nominal problem is
$\mathsf{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 $\Sigma^p_3$-completeness for variations of
recoverable robust problems and
$\mathsf{PSPACE}$-completeness for several online graph
problems with a map.},
cin = {121110 / 121220 / 080060},
ddc = {004},
cid = {$I:(DE-82)121110_20140620$ / $I:(DE-82)121220_20140620$ /
$I:(DE-82)080060_20170720$},
pnm = {GRK 2236 - GRK 2236: Unsicherheit und Randomisierung in
Algorithmen, Verifikation und Logik. (282652900)},
pid = {G:(GEPRIS)282652900},
typ = {PUB:(DE-HGF)11},
doi = {10.18154/RWTH-2025-09741},
url = {https://publications.rwth-aachen.de/record/1021909},
}
Gast ::