Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...

Details

Autor(en) / Beteiligte
Titel
On the hardness of computing local optima : = Über die Schwierigkeit der Berechnung Lokaler Optima
Erscheinungsjahr
2011
Verknüpfte Titel
Beschreibungen/Notizen
  • Tag der Verteidigung: 08.04.2011
  • Paderborn, Univ., Diss., 2011
  • ger: 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_{k-par} beschränken hierbei simultan die maximale Länge p jedes Constraints, das maximale Auftreten q jeder Variable und deren Wertigkeit r; zusätzlich ist die Menge der Constraints k-partit. Wir konzentrieren uns auf Härteergebnisse und zeigen in Kapitel 6 mittels tighter Reduktionen von CIRCUIT/FLIP die PLS-Vollständigkeit von (3,2,3)-MCA_{3-par}, (2,3,6)-MCA_{2-par} und (6,2,2)-MCA. Abschließend untersuchen wir in Kapitel 7 die Komplexität der Berechnung lokal optimaler Lösungen von gewichteten Standard-Mengenproblemen wie SETPACKING, SETCOVER und vieler anderer Probleme, wie sie in [SP1]-[SP10] im Buch von Garey und Johnson [Seite 221ff.] zusammengefasst sind.
  • eng: 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_{k-par} simultaneously limit the maximum length p of each constraint, the maximum appearance q of each variable and its valence r; additionally, the set of constraints is k-partite. We focus on hardness results and show PLS-completeness of (3,2,3)-MCA_{3-par}, (2,3,6)-MCA_{2-par} and (6,2,2)-MCA, using tight reductions from CIRCUIT/FLIP in Chapter 6. Finally, in Chapter 7 we study the complexity of computing locally optimal solutions of weighted standard set problems such as SETPACKING, SETCOVER, and many more, as pooled in problems [SP1]-[SP10] in the book of Garey and Johnson [page 221ff.].
Sprache
Englisch
Identifikatoren
OCLC-Nummer: 1106623178, 1106623178
Titel-ID: 990014111770106463
Format
XI, 154 S.

Lade weitere Informationen...