TY  - THES
A3  - Monien, Burkhard
A3  - Meyer auf der Heide, Friedhelm
A3  - Röglin, Heiko
AB  - Die lokale Suche ist einer der erfolgreichsten Ansätze zur Lösung schwerer Optimierungsprobleme. Bei der lokalen Suche ist jeder Lösung eine Menge von Nachbarlösungen zugeordnet. Gesucht ist ein lokales Optimum, das heißt eine Lösung, die keinen besseren Nachbarn hat. Um die Komplexität der Berechnung lokaler Optima zu kapseln, haben Johnson et al. (JCSS,1988) die Klasse PLS eingeführt. Kurz danach zeigten Schäffer et al. (JOC,1991) PLS-Vollständigkeit für verschiedene lokale Suchprobleme einschließlich des Problems LocalMax-Cut auf Graphen unbeschränkten Grades mit FLIP-Nachbarschaft, in der ein Knoten die Partition wechselt. Darüber hinaus zeigten sie zwei weitere Ergebnisse für LocalMax-Cut: Erstens, es hat die Eigenschaft, dass es eine unendliche Familie von Instanzen und initialen Lösungen gibt, für die jede Folge verbessernder Schritte, die in einem lokalen Optimum endet, exponentiell lang ist (All-exp Eigenschaft). Zweitens, das Problem, ein lokales Optimum zu berechnen, das ausgehend von einem Paar aus Instanz und initialer Lösung via verbessernder Schritte erreichbar ist (kurz: SAP), ist PSPACE-vollständig. Auf der anderen Seite zeigte Poljak (JOC,1995), dass höchstens quadratisch viele verbessernde Schritte für LocalMax-Cut auf kubischen Graphen möglich sind bis ein lokales Optimum erreicht wird. Die vorliegende Arbeit liefert drei Komplexitätsergebnisse für LocalMax-Cut. Erstens behält es die All-exp Eigenschaft auch wenn es auf Graphen mit Höchstgrad vier eingeschränkt wird. Zweitens ist das SAP PSPACE-vollständig auf Graphen mit Höchstgrad vier. Drittens ist die Berechnung eines lokalen Optimums PLS-vollständig für Graphen mit Höchstgrad fünf.
AU  - Tscheuschner, Tobias
DA  - 2012
DP  - Universität Paderborn
LA  - ger
N1  - Tag der Verteidigung: 05.07.2012
N1  - Paderborn, Univ., Diss., 2012
PB  - Veröffentlichungen der Universität
PY  - 2012
T2  - Institut für Informatik
TI  - The complexity of local max-cut
UR  - https://nbn-resolving.org/urn:nbn:de:hbz:466:2-9222
Y2  - 2025-04-30T00:27:13
ER  -