Erweiterung von Ansätzen zur Verläßlichkeit - Netzerzeugungsspiele, Echtzeitaublaufplanung und Robuste Optimierung

Das erste Kapitel widmet sich einer Familie von Netzerzeugungsspielen. Netzerzeugungsspiele dienen der grobkörnigen Analyse von Netzwerken für die detailierte Daten nicht vorliegen, oder grundsätzlich nicht gewonnen werden können. Ein typisches Beispiel sind Soziale Netze. In den hier untersuchten Spielen wird das Netzwerk von den Knoten als den Spielern selbst gebildet. Paare von Knoten können Kanten zwischen sich einrichten oder abbrechen. Jedem Knoten entstehen feste Kosten für jede zum ihm inzidente Kante. Ein Knoten profitiert jedoch global vom Netzwerk. Jeder Knoten zieht einen Nutzen daraus, zu jedem anderen Knoten direkt oder indirekt verbunden zu sein. Dieser Nutzen ist abhängig von der Distanz der beiden Knoten im Netzwerk. Bisher konnten nur Spiele analysiert werden, in denen sich diese Distanz linear auf den Nutzen auswirkt. Wir können u.a. den Preis der Anarchie bei exponentiellen Nutzenfunktionen exakt auf 2 bestimmen. Dieses Ergebnis beruht auf einer graphentheoretischen Charakterisierung stabiler Zustände. Hiermit gelingt es auch zu zeigen, dass diese Prozesse zykeln können. Im zweiten Kapitel beschreiben wir einen approximativen Zulässigkeitstest für das sporadische Echtzeit-Ablaufplanungsproblem auf mehreren identischen Prozessoren. Eine Instanz diese Problems besteht aus einer potenziell unendlichen Folge von Aufträgen, die von einer festen Anzahl Prozessoren bearbeitet werden. Die Zuweisung der Aufträge auf die Prozessoren muss auf Grund des Echtzeitcharakters der Anwendung gemäß einer einfachen Politik erfolgen. Da die Anwendungen zudem sicherheits-kritisch sind, muss im Voraus sichergestellt werden, dass jeder Auftrag fristgerecht abgeschlossen wird. Angesichts der enormen Anzahl an Aufträgen (die häufig sogar als unendlich modelliert wird) muss ein Zulässigkeitstest dies anhand einer sehr kompakten, insbesondere endlichen, im sporadischen Fall unvollständigen Beschreibung der Instanz beurteilen. Unser Test entscheidet entweder, dass für eine Instanz kein zulässiger Ablaufplan existiert, oder dass die Instanz durch einen Ablaufplan, bei dem stets der Auftrag mit der nächstliegenden Frist als erster bearbeitet wird, auf annähernd doppelt so schnellen Prozessoren zuverlässig gelöst wird. Die Existenz eines solchen approximativen Zulässigkeitstest wurde seit den neunziger Jahren vermutet. Seither ist ebenfalls bekannt, dass die hier in Anspruch genommene Geschwindigkeitserhöhung die kleinst mögliche ist, da bereits die einfache Ablaufregel diese Erhöhung erforderlich macht. Der vorliegende Test ist damit der erste bestmögliche Test seiner Art für mehr als einen Prozessor. Im letzten Kapitel beschäftigen wir uns mit Robuster Optimierung. Robuste Optimierung ist ein spezieller Ansatz im Bereich der Optimierung unter Informationsdefizit. Anstelle verlässlicher Daten ist eine (im Allgemeinen unendliche) Menge von Szenarien gegeben. Ein leitendes Beispiel sind verspätungsresistente Fahrpläne. Die klassische robuste Optimierung sucht nach Lösungen, die in jedem dieser Szenarien zulässig sind. Dies führt zu unzumutbar konservative Lösungen. Klassische robuste Fahrpläne etwa weisen unverhältnismäßig große Pufferzeiten auf. Wir entwickeln dagegen den Begriff der Wiederherstellungfreundlichkeit (Recoverable Robustness). Eine wiederherstellungsfreundliche Lösung lässt sich mit geringem Aufwand in jedem anzunehmenden Szenario in eine zulässige Lösung verwandeln. Wir zeigen, dass dieser Begriff die Vorteile der klassischen Robustheit, insbesondere die Gütegarantie und die Lösbarkeit erhält, und dennoch weit weniger konservative Lösungen als der klassische Ansatz ermöglicht. Die Wiederherstellungsfreundlichkeit erlaubt zudem die Anwendung auf Praxisprobleme, die der klassischen robusten Optimierung vorenthalten sind. Eine wichtige Spezialisierung dieses Begriffs ist die robuste Netzpufferung. Dies ist ein verhältnismäßig einfach zu implementierendes, exaktes Verfahren, das in der Zwischenzeit bereits Anwendung in der Gleiszuweisung gefunden hat. Dort hat die Methode eine Reduzierung der Verspätung um ein Viertel bewirkt. Für ganzzahlige Varianten der robusten Netzpufferung beweisen wir u.a. Nicht-Approximierbarkeit. Neben den Anwendungs- und Modellierungsvorteilen eröffnet die Wiederherstellungsfreundlichkeit eine neue, polyedrische Sichtweise auf die lineare Optimierung unter Informationsdefizit. Diese Perspektive erlaubt es im Vorhinein den Bereich aussergewöhnlich großer Störungen zu bestimmen, in dem wiederherstellungsfreundliche Lösung immer noch beherrschbar bleiben. Wir führen an einer Reihe von Beispielen die Anwendung der Wiederherstellungsfreundlichkeit insbesondere bei der Planung von Verkehrssystemen vor. Im Zuge dessen bestimmen wir auch die Komplexität des Verspätungsmanagements, und modellieren einen durch die Anwendung motivierten alternativen Ansatz mit geringerer Komplexität.We discuss three different, classical concepts of reliability: the analysis of network creation games, feasibility tests for real-time scheduling, and robust optimization. In each case a substantial extension of the concept yields a significant advance both with respect to applicability and to mathematical insight. All concepts belong to the broader field of combinatorial and linear optimization and discrete mathematics. Still, each topic belongs to a separate special research area, and requires a different method. In the first chapter we analyze a family of network creation games. Network creation games are a high-level tool to understand the structure of networks which cannot be apprehended explicitly and in full detail. Typical examples of such a networks are social network. We consider settings in which the network is created by selfish, myopic players corresponding to the vertices of the network. Each pair of vertices can establish an edge among them. A vertex has to cover a fixed cost for each of its incident edges. In contrast to this local cost the vertices have a global benefit from the network. Each vertex has an income from any other vertex to which it is directly or indirectly connected. The value of this income is given by some function of the distance between the two vertices in the network. An edge is stable when both incident vertices have a better payoff in the current network with the edge than without it. Hitherto, such a setting could only be analyzed for an income function that depends linearly on the distance. We consider exponentially decaying income functions. This process has originally been proposed in economics to analyze social networks of cooperation or information exchange. We show that the process has a positive probability to cycle. We reduce the creation rule functions to graph theoretic criteria. Moreover, these criteria can be evaluated locally. This allows us to reveal the structure of all stable states. In addition, the question for the price of anarchy can be reduced to counting the maximum number of edges of a stable graph. This allows to determine the price of anarchy exactly. It equals 2. In the second chapter we propose an approximate feasibility test for sporadic, multiprocessor real-time scheduling. An instance of this problem consists of a potentially infinite set of jobs that have to be executed on fixed set of processors. The real-time character of the applications requires simple scheduling policies. Moreover, the applications are typically safety-critical. Therefore, it must be guaranteed in advance that every job meets its deadline. Due to the enormous number of jobs this test must be based on a compact, in the sporadic case even vague description of the job sequence. For any sporadic real-time scheduling instance our feasibility test either returns that the given instance cannot be scheduled at all on the given platform of processors, or that it is scheduled feasibly by the Earliest-Deadline-First policy (EDF) on processors with almost double-speed. Also it has been apparent since then that almost double speed is the least possible speed-up factor, because EDF already requires this speed-up to feasibly schedule every feasible instance. Robust Optimization is the subject of the last chapter. It is a specific concept for optimization under imperfect information. Instead of reliable data we are given a (usually infinite set) of scenarios. A guiding example for our work are delay resistant timetables. Classical Robustness seeks solutions that are feasible in each scenario. This yields unacceptably conservative solutions. Classical robust timetables for example make excessive use of buffer times. In contrast we develop the notion of Recoverable Robustness. A recovery robust solution can be recovered in every likely scenario by a limited effort. We show that this notion maintains the advantages of classical robustness, in particular tractability and a quality guarantee, while it produces substantially less conservative solutions. Recoverable Robustness is applicable to real-world problems that cannot be modeled convincingly in the classical terms. An important special case of this notion is robust network buffering. It has been used for train platforming in the mean-time, reducing delay by a forth. For the integer variants of network buffering we prove inapproximability. Besides, we unfold a polyhedral perspective to recoverable robustness. This yields a new approach to linear programming under uncertainty. It allows to a priori determine the region of large disturbances in which a recovery robust solutions stays recoverable. We exemplify Recoverable Robustness with a number of applications mostly from public transport design. In this context we prove PSPACE-hardness for the delay management problem. We also model delay resistant timetabling with respect to a simpler strategy for delay management which is motivated by the application