Exakte Analyse von Heuristiken
Final Report Abstract
Zahlreiche fundamentale Berechnungsprobleme sind NP-schwer; das bedeutet, daß für diese Probleme trotz intensivster Forschungsbemühungen seit den 1950er Jahren keine effizienten Algorithmen bekannt sind, die jede mögliche Eingabeinstanz optimal lösen. Daher werden in der Praxis häufig Heuristiken eingesetzt, welche zwar nicht jede Probleminstanz optimal, aber doch „die meisten" zufriedenstellend lösen sollen. Heuristiken beruhen häufig auf Ideen aus verschiedensten Bereichen, z.B. der statistischen Physik, und werden nicht exakt, sondern zumeist nur z.B. experimentell Untersucht. Daher war es die Zielsetzung dieses Projektes, Heuristiken mit exakten mathematischen Methoden zu studieren. Ein zentrales Hilfsmittel sollten dabei zufällige diskrete Strukturen sein. Im Projektabschnitt Spektraltechniken wurden Heuristiken untersucht, die zur Lösung eines kombinatorischen Problems, etwa eines Graphenpartitionierungsproblems, Methoden aus der Linearen Algebra einsetzen. Diese Algorithmen beruhen auf der Idee, die Eingabeinstanz durch eine Matrix darzustellen und mit Hilfe von Eigen- oder Singulärwertberechnungen eine Lösung des kombinatorischen Problems zu erstellen. Im Projektverlauf konnten verbesserte Heuristiken zur Graphenpartitionierung entwickelt und auf aussagekräftigen Zufallsmodellen von Eingabeinstanzen exakt analysiert werden. Im Vergleich zur existierenden Literatur liegt die wesentliche Verbesserung darin, daß diese Algorithmen auch auf dünne Graphen (etwa mit einer zur Knotenzahl proportionalen Kantenzahl) anwendbar sind. Darüber hinaus konnte eine fundamentale Beziehung zwischen Spektraleigenschaften und kombinatorischen Eigenschaften von Graphen hergestellt werden; dieses Resultat beantworte eine von Chung und Graham aufgeworfene offene Frage. Untersuchungsgegenstand im Projektabschnitt Phasenübergänge waren Struktureigenschaften zufälliger Eingabeinstanzen und Auswirkungen derselben auf die algorithmische Lösbarkeit der Instanzen. Wir konnten zunächst Fortschritte erzielen in Bezug auf einige fundamentale kombinatorische Fragestellungen, wie z.B. das Problem, die chromatische Zahl eines Zufallsgraphen mit gegebener Knoten- und Kantenzahl zu bestimmen. Darüber hinaus konnten wir wesentliche Hypothesen, die in Zusammenhang mit dem aus der statistischen Physik motivierten Survey-Propagation-Algorithmus stehen, exakt beweisen. Schließlich wurde ein verwandter Algorithmus für das Graphenfärbungsproblem, der Belief-Propagation-Algorithmus, in Beziehung zu Spektralmethoden gesetzt und damit erstmals für eine nicht-triviale Klasse von Eingabeinstanzen exakt analysiert. Thema des Projektabschnittes Zufällige Strukturen und worst case-Analyse war die Frage, inwiefern sich Analysen von Heuristiken auf zufälliger Eingabe in worst cose-Analysen umwandeln lassen. Es geht also darum, möglichst umfassende Strukturbedingungen herauszuarbeiten, unter denen die Heuristik das Gewünschte leistet. Als wesentliches Hilfemittel haben wir dazu das Konzept der regulären Partition von Graphen studiert. Eine reguläre Partition eines Graphen ist dabei eine Approximation des Graphen durch eine möglichst kleine Zahl von Graphen, in denen die globale Verteilung der Kanten der eines zufälligen Graphen ähnelt (quasi-zufällige Graphen). Es wurde ein Regularitätskonzept entwickelt, das die Gradverteilung des Graphen in Betracht zieht, und daher im Gegensatz zu früher bekannten Konzepten auch auf Graphen mit äußerst irregulärer Gradverteilung anwendbar ist (Stichwort „power law"). Wir konnten zeigen, daß unter einer einfach strukturellen Nebenbedingung (Beschränktheitsbedingung) eine reguläre Partition mit einer beschränkten Zahl von Klassen effizient berechnet werden kann. Dieses Resultat ermöglicht, zahlreiche algorithmische Ergebnisse für zufällige Graphen auf Graphen zu übertragen, die einfach nur die Beschränktheitsbedingung erfüllen.
Publications
-
Random k-SAT: the limiting probability for satisfiability for moderately growing k. Electronic Journal on Combinatorics N2
Amin Coja-Oghlan, Alan Frieze
-
Separating populations with wide data: a spectral analysis. Proc. 18th ISAAC, Springer LNCS 4835, 439-451
Avrim Blum, Amin Coja-Oghlan, Alan Frieze, Shuheng Zhou
