Dissertation/Thesis Abstract

Algorithm and Mechanism Design for Congested Networks
by Bjelde, Antje, Ph.D., Technische Universitaet Berlin (Germany), 2018, 130; 10869413
Abstract (Summary)

In dieser Arbeit betrachten beschäftigen wir uns mit dem Problem der Reduzierung von starker Auslastung in Netzwerken. Zuerst betrachten wir allgemeine Ressourcenverteilungsprobleme, in welchen Nutzer gemeinsam eine Menge von Ressourcen mit negativen Skaleneffekten benutzt. Die zulässigen Verteilungen für jeden Nutzer bestehen aus einer nutzerspezifische Menge von Teilmengen der Ressourcen. Die Kosten für jede Ressource sind durch ein Polynom der Ordnung d bestimmt, welches die Gesamtnutzung einer Ressource auf ihre Kosten abbildet. Wir präsentieren einen lokalen Suchalgorithmus zur Reduzierung der Gesamtkosten für welchen wir eine obere und untere Schranke an die Lokalisierungslücke angeben. Zusätzlich geben wir konkrete Werte der Lokalisierungslücke für kleine d. Wir berechnen außerdem die allgemeine Approximationsgarantie für den linearen Fall und zeigen APX-Schwere mit einer unteren Schranke welche sich erhöht falls die Unique Games Vermutung wahr ist. Weiterhin betrachten wir das Problem der unabhängigen Auswahl, bei dem sich eine Menge von Spielern untereinander nominiert und wir eine Spielerin mit einer großen Anzahl von Nominierungen auswählen wollen. Jeder Auswahlmechanismus soll Unabhängigkeit sichern, das heißt, dass die Nominierungen einer Spielerin keinen Einfluss auf ihre Wahrscheinlichkeit ausgewählt zu werden haben. Es ist bekannt, dass kein deterministischer Mechanismus eine positive Approximationsgüte garantieren kann, weswegen wir die Exaktheitsbedingung lockern und erlauben, dass manchmal, aber nicht immer, auch weniger als die vorgegebene Menge an Spielern ausgewählt werden kann. Wir führen einen Mechanismus ein, welcher ein bewiesen bestmögliches Ergebnis für die deterministische Auswahl von bis zu zwei Spielern gibt. Für die randomisierte Variante geben wir eine Garantie für die Anzahl von Nominierungen in Erwartung. Weiterhin zeigen wir einen bestmöglichen Mechanismus für die Auswahl von bis zu zwei aus drei Spielern. Wir geben zudem untere und obere Schranken um genau zwei Spieler auszuwählen und verallgemeinern und analysieren unsere Mechanismen für die Auswahl einer größeren Anzahl von k Spielern. Zusätzlich gibt unsere Arbeit eine Zuteilungsunterroutine, welche eine schnelle und einfache Lösung für das Problem auf faire Art und Weise Repräsentanten proportional zu Gruppengrößen auszuwählen bietet. Schließlich betrachten wir das online Fahrdienstproblem auf der Linie. Nutzer erscheinen in einer fortlaufenden Art und Weise an einer beliebigen Stelle auf dem reellen Zahlenstrahl und fragen an, zu einem anderen Ort auf dem Zahlenstrahl transportiert zu werden. Ein Zusteller mit vorgegebener Kapazität, welcher im Nullpunkt startet, nimmt die Nutzer auf und bringt sie, mit oder ohne temporäre Unterbrechung, zu ihrem Ziel. Unser Ziel ist es, die Gesamtdauer, d.h. die Gesamtzeit, welche der Server braucht bis der letzte Auftrag ausgeführt wurde, zu minimieren. Wir präsentieren einen kompetitiven Algorithmus für das online Fahrdienstproblem mit Unterbrechungen auf der Linie und beweisen eine verbesserte untere Schranke für den Fall ohne Unterbrechungen. Weiterhin zeigen wir, dass eine leicht modifizierte Variante des Algorithmus die Kompetitivitätsgüte beibehält. Wir betrachten zudem das offline Problem und zeigen, dass wir Instanzen konstruieren können, so dass der Server beliebig viele Richtungswechsel auf der Linie machen muss und geben ein dynamisches Programm an, welches die minimale Vollendungszeit für dieses Problem in quadratischer Zeit berechnet. Im Gegensatz hierzu zeigen wir, dass das offline Fahrdienstproblem ohne Unterbrechungen mit Kapazität eins NP-vollständig ist.

Indexing (document details)
Advisor: Blath, Jochen
Commitee: Klimm, Max, Fischer, Felix, Skutella, Martin
School: Technische Universitaet Berlin (Germany)
School Location: Germany
Source: DAI-C 81/1(E), Dissertation Abstracts International
Source Type: DISSERTATION
Subjects: Mathematics
Keywords: Algorithm , Mechanism design, Congested networks
Publication Number: 10869413
ISBN: 9781392786109
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy
ProQuest