Zur Seitenansicht
 

Titelaufnahme

Titel
Über die Schwierigkeit der Berechnung Lokaler Optima
AutorDumrauf, Dominic In der Gemeinsamen Normdatei der DNB nachschlagen
PrüferMonien, Burkhard In der Gemeinsamen Normdatei der DNB nachschlagen ; Meyer auf der Heide, Friedhelm In der Gemeinsamen Normdatei der DNB nachschlagen
Erschienen2011
HochschulschriftPaderborn, Univ., Diss., 2011
Anmerkung
Tag der Verteidigung: 08.04.2011
SpracheEnglisch ; Deutsch
DokumenttypDissertation
URNurn:nbn:de:hbz:466:2-150 Persistent Identifier (URN)
Dateien
On the hardness of computing local optima [2.19 mb]
Abstract of Dissertation [0.15 mb]
Zusammenfassung der Dissertation [0.18 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

In dieser Arbeit untersuchen wir die Komplexität der Berechnung lokal optimaler Lösungen von Problemen aus den Bereichen der Spieltheorie und der Optimierung. Für unsere Untersuchungen verwenden wir das Framework PLS (Abkürzung für "Polynomialzeit lokale Suche"), wie von Johnson, Papadimtriou und Yannakakis eingeführt. In der Spieltheorie sind Congestion Games ein weit verbreitetes und akzeptiertes Modell um das Verhalten und die Performanz von großen verteilten Netzwerken mit autonomen Teilnehmern zu untersuchen. Die Klasse der Restricted Network Congestion Games ist eine Teilklasse der Congestion Games bei der für jeden Spieler eine Menge von Kanten existiert, die er nicht verwenden darf. In Kapitel 5 zeigen wir mittels einer tighten Reduktion von MAXCUT, dass die Berechnung eines Nash Equilibriums in einem Restricted Network Congestion Game mit zwei Spielern PLS-vollständig ist. Aus dem Bereich der Optimierung untersuchen wir die Komplexität der Berechnung lokal optimaler Lösungen des MAXIMUM CONSTRAINT ASSIGNMENT (abgekürzt MCA) Problems und von gewichteten Standard-Mengenproblemen. Die Parameter in (p,q,r)-MCA_

Zusammenfassung (Englisch)

In this thesis, we investigate the complexity of computing locally optimal solutions of problems arising in the fields of game theory and optimization. For our investigation, we use the framework of PLS (short for "Polynomial-time Local Search"), as introduced by Johnson, Papadimtriou, and Yannakakis. In game theory, congestion games are a widely accepted model to investigate the behavior and performance of large-scale distributed networks with autonomous participants. The class of restricted network congestion games is a subclass of congestion games where for each player there exists a set of edges which he is not allowed to use. In Chapter 5, we show that computing a Nash equilibrium in a restricted network congestion game with two players is PLS-complete, using a tight reduction from MAXCUT. From the field of optimization, we investigate the complexity of computing locally optimal solutions of the MAXIMUM CONSTRAINT ASSIGNMENT (in short MCA) problem and of weighted standard set problems. The parameters in (p,q,r)-MCA_