TY  - THES
A3  - Monien, Burkhard
A3  - Meyer auf der Heide, Friedhelm
AB  - 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_
AU  - Dumrauf, Dominic
DA  - 2011
DP  - Universität Paderborn
LA  - eng
N1  - Tag der Verteidigung: 08.04.2011
N1  - Paderborn, Univ., Diss., 2011
PB  - Veröffentlichungen der Universität
PY  - 2011
T2  - Institut für Informatik
TI  - On the hardness of computing local optima
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-150
Y2  - 2026-02-05T15:26:50
ER  -