h1

001021909 001__ 1021909
001021909 005__ 20251202085502.0
001021909 0247_ $$2HBZ$$aHT031326300
001021909 0247_ $$2Laufende Nummer$$a44779
001021909 0247_ $$2datacite_doi$$a10.18154/RWTH-2025-09741
001021909 037__ $$aRWTH-2025-09741
001021909 041__ $$aEnglish
001021909 082__ $$a004
001021909 1001_ $$0P:(DE-82)IDM05251$$aGrüne, Christoph Manfred$$b0$$urwth
001021909 245__ $$aComputational complexity of problems in robust, bilevel and online optimization$$cvorgelegt von Christoph Manfred Grüne, Master of Science$$honline
001021909 260__ $$aAachen$$bRWTH Aachen University$$c2025
001021909 300__ $$a1 Online-Ressource : Illustrationen
001021909 3367_ $$02$$2EndNote$$aThesis
001021909 3367_ $$0PUB:(DE-HGF)11$$2PUB:(DE-HGF)$$aDissertation / PhD Thesis$$bphd$$mphd
001021909 3367_ $$2BibTeX$$aPHDTHESIS
001021909 3367_ $$2DRIVER$$adoctoralThesis
001021909 3367_ $$2DataCite$$aOutput Types/Dissertation
001021909 3367_ $$2ORCID$$aDISSERTATION
001021909 502__ $$aDissertation, RWTH Aachen University, 2025$$bDissertation$$cRWTH Aachen University$$d2025$$gFak09$$o2025-10-07
001021909 500__ $$aVeröffentlicht auf dem Publikationsserver der RWTH Aachen University
001021909 5203_ $$aDiese Arbeit befasst sich mit der Komplexität von robuster, zweistufiger und Echtzeit-Optimierung. In diesen Gebieten beschäftigen wir uns mit min-max (beziehungsweise mehrstufigen) Problemen aus den beliebten Themenbereichen von Netzwerk-Untersagung, Wichtigste-Knoten-Probleme, Min-Max-Bedauern-Optimierung, Zwei-Phasen-Anpassbarkeit-Optimierung, wiederherstellbar-robuster Optimierung und Echtzeit-Optimierung. Obwohl diese Gebiete seit mehr als zwei Jahrzehnten erforscht werden und man natürlicherweise die meisten der Probleme als vollständig für die unteren Stufen der polynomiellen Hierarchie oder polynomiellen Platz einschätzt, sind kaum exakte Vollständigkeitsresultate bekannt. Wir adressieren diese Lücke, indem wir zwei Reduktionsrahmenstrukturen entwickeln, um die gemeinsamen Strukturen von kombinatorischen Problemen zu analysieren, die eine Art von Unsicherheit enthalten, die wiederum ein ähnliches Verhalten in ihrer Komplexität induzieren. Die Reduktionsrahmenstrukturen funktionieren wie folgt. Zuerst definieren wir kombinatorische Probleme im Allgemeinen, diese nennen wir auch nominale Probleme. Basierend auf dieser Definition des nominalen Problems können wir Definitionen für die allgemeineren Varianten ableiten, die bestimmte Arten von Unsicherheiten modellieren. Die übergeordnete Idee ist nun, die Reduktionen zwischen den nominalen Problemen auf gemeinsame Eigenschaften zu untersuchen, die uns helfen, Reduktionen zwischen den allgemeineren Varianten herzuleiten. Demzufolge definieren wir solch eine Art von Reduktion und zeigen, dass diese Eigenschaften bereits von existierenden Reduktionen oder geringen Modifikationen dieser erfüllt werden. Wir wenden die Rahmenstrukturen auf $\mathsf{NP}$-vollständige nominale Probleme an und leiten Komplexitätsresultate für die Vollständigkeit in der polynomiellen Hierarchie oder der Komplexitätsklasse $\mathsf{PSPACE}$ ab. Die erste Rahmenstruktur beschäftigt sich mit Teilmengensuchproblemen (abgekürzt TSP), wir nennen die Rahmenstruktur daher TSP-Rahmenstruktur. Ein Teilmengensuchproblem ist ein kombinatorisches Problem, das aus Instanzen $\mathcal{I}$ besteht, die wiederum ein Universum $\mathcal{U}$ zusammen mit weiteren Informationen enthalten. Eine Lösung $S \in \mathcal{S}$ ist eine Teilmenge des Universums, d.h. $S \subseteq \mathcal{U}$.Die entsprechenden TSP-Reduktionen sind gewöhnliche Reduktionen zusammen mit einer zusätzlichen injektiven Funktion, die das Universum des einen Problems in das des anderen Problems abbilden. Tatsächlich erfüllen viele existierende Reduktionen auf der $\mathsf{NP}$-Ebene genau diese TSP-Eigenschaft. Basierend auf diesem Begriff können wir die TSP-Reduktionen zwischen den nominalen Probleme zu Reduktionen zwischen den Problemversionen im Gebiet von robuster und zweistufiger Optimierung aufrüsten. Wir wenden diese Rahmenstruktur konkret auf die Gebiete von Untersagung, Min-Max-Bedauern-Optimierung, Zwei-Phasen-Anpassbarkeit-Optimierung, und wiederherstellbar-robuster Optimierung an und zeigen $\Sigma^p_2$- und $\Sigma^p_3$-Vollständigkeit für die entsprechenden Probleme, wenn das nominale Problem $\mathsf{NP}$-vollständig ist.In der zweiten Rahmenstruktur geht es um kombinatorische Probleme, die mit einem unterliegenden Universum und verschachtelten Relationen über dem Universum beschrieben werden können. Die entsprechende Reduktion nennen wir Universum-Apparat-Reduktion. Die besondere Eigenschaft einer Universum-Apparat-Reduktion von einem Problem $A$ zu einem Problem $B$ ist, dass ein Apparat für jedes Universumselement und jedes Relationselement des Problems $A$ erzeugt wird. Diese Apparate bestehen aus den Universums- und Relationselementen des Problems $B$ und sind disjunkt. Basierend auf dieser Reduktion sind wir fähig, $\Sigma^p_3$-Vollständigkeit für Variationen von wiederherstellbar-robuste Problemen und $\mathsf{PSPACE}$-Vollständigkeit von Echtzeit-Graph-Problemen mit einer Karte zu zeigen.$$lger
001021909 520__ $$aThis 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.$$leng
001021909 536__ $$0G:(GEPRIS)282652900$$aGRK 2236 - GRK 2236: Unsicherheit und Randomisierung in Algorithmen, Verifikation und Logik. (282652900)$$c282652900$$x0
001021909 588__ $$aDataset connected to Lobid/HBZ
001021909 591__ $$aGermany
001021909 7001_ $$0P:(DE-82)IDM00088$$aRossmanith, Peter$$b1$$eThesis advisor$$urwth
001021909 7001_ $$0P:(DE-82)1022670$$aGoerigk, Marc$$b2$$eThesis advisor
001021909 8564_ $$uhttps://publications.rwth-aachen.de/record/1021909/files/1021909.pdf$$yOpenAccess
001021909 8564_ $$uhttps://publications.rwth-aachen.de/record/1021909/files/1021909_source.zip$$yRestricted
001021909 909CO $$ooai:publications.rwth-aachen.de:1021909$$pdnbdelivery$$pdriver$$pVDB$$popen_access$$popenaire
001021909 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
001021909 9141_ $$y2025
001021909 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM05251$$aRWTH Aachen$$b0$$kRWTH
001021909 9101_ $$0I:(DE-588b)36225-6$$6P:(DE-82)IDM00088$$aRWTH Aachen$$b1$$kRWTH
001021909 9201_ $$0I:(DE-82)121110_20140620$$k121110$$lLehrstuhl für Algorithmen und Komplexität (Informatik 1)$$x0
001021909 9201_ $$0I:(DE-82)121220_20140620$$k121220$$lLehr- und Forschungsgebiet Theoretische Informatik$$x1
001021909 9201_ $$0I:(DE-82)080060_20170720$$k080060$$lGraduiertenkolleg UnRAVeL$$x2
001021909 961__ $$c2025-12-01T15:24:31.440076$$x2025-11-18T12:37:59.989220$$z2025-12-01T15:24:31.440076
001021909 9801_ $$aFullTexts
001021909 980__ $$aI:(DE-82)080060_20170720
001021909 980__ $$aI:(DE-82)121110_20140620
001021909 980__ $$aI:(DE-82)121220_20140620
001021909 980__ $$aUNRESTRICTED
001021909 980__ $$aVDB
001021909 980__ $$aphd