Details

Autor(en) / Beteiligte

• Tscheuschner, Tobias
• Monien, Burkhard
• Meyer auf der Heide, Friedhelm
• Röglin, Heiko

Titel

The complexity of local max-cut [Elektronische Ressource]

Erscheinungsjahr

2012

Link zum Volltext

• Hochschulschriften Visual Library - Scan2Web Hochschulschriften UB Paderborn (s2w-hsspadubpb)
• Volltext

  kostenfrei

Link zu anderen Inhalten

• Volltext

Verknüpfte Titel

Beschreibungen/Notizen

• Tag der Verteidigung: 05.07.2012
• Paderborn, Univ., Diss., 2012
• ger: 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.
• eng: Local search is one of the most successful approaches for solving hard optimization problems. In local search, a set of neighbor solutions is assigned to every solution and one asks for a local optimum, i.e., a solution that has no better neighbor. To encapsulate the complexity of finding local optima, Johnson et al. (JCSS,1988) introduced the complexity class PLS. Shortly afterwards, Schäffer et al. (JOC,1991) showed PLS-completeness for several local search problems including LocalMax-Cut on graphs with unbounded degree with a FLIP-neighborhood in which one node changes the partition. Moreover, they showed two further results for LocalMax-Cut: First, there is an infinite family of instances and solutions for which every sequence of improving steps that ends up in a local optimum has exponential length (all-exp property). Second, the StandardAlgorithmProblem (SAP), i.e., the problem of finding a local optimum that is reachable from a given pair of an instance and initial solution via improving steps, is PSPACE-complete. On the positive side, Poljak (JOC,1995) showed that there are at most quadratically many improving steps possible for LocalMax-Cut on cubic graphs. This thesis provides three complexity results for LocalMax-Cut. First, it has the all-exp property if restricted to graphs with maximum degree four. Second, the SAP is PSPACE-complete for graphs with maximum degree four. Third, finding a local optimum is PLS-complete for graphs with maximum degree five.