- Stabile Mengen und spezielle Graphenklassen
- Kombinatorische Online-Planung
- Evolution und Phasenübergänge
- Zufall bei Entwurf und Analyse von diskreten Algorithmen
- Geometrie und Kombinatorik von 0/1-Polytopen
- Enumeration und zufälliges Erzeugen
Projekt 1: Stabile Mengen und spezielle Graphenklassen
Stabile Mengen in Graphen bilden eines der wichtigen Modelle in der ganzzahligen Optimierung. Sie haben vielfältige Anwendungen. Das Stabile-Mengen-Problem ist im Allgemeinen NP-schwer und auch in der Praxis nicht einfach zu lösen. Die polynomiale Lösbarkeit des Stabile-Mengen-Problems ist nur für wenige Graphenklassen bekannt. Unter diesen sind perfekte Graphen die strukturell interessantesten, da Charakterisierungen perfekter Graphen eine Schnittstelle zwischen Graphentheorie, Polyedertheorie, Informationstheorie und ganzzahliger Programmierung bilden und Einblicke in Zusammenhänge dieser Gebiete liefern:
The relation between perfect graphs and information theory is probably deeper than well-known (Simonyi, 2001).
Perfekte Graphen sind u. a. mittels der Graph-Entropie charakterisiert; der sog. Imperfektheitsgrad kann durch die Graph-Entropie ausgedrückt werden, die Graph-Entropie wiederum als Entropie des Stabile-Mengen-Polytops. Dies zeigt den engen Zusammenhang zwischen polyedertheoretischen und informationstheoretischen Charakterisierungen perfekter Graphen. Der Schwerpunkt des Projektes liegt auf der Untersuchung von Relaxierungen dieser Konzepte auf Oberklassen perfekter Graphen.
Projekt 2: Kombinatorische Online-Planung
Im Gegensatz zur klassischen Optimierung geht man in der Online-Optimierung davon aus, dass nicht sämtliche Daten eines Problems vorab bekannt sind. Somit müssen Entscheidungen auf der Basis unvollständigen Wissens getroffen werden. Die Eingabe wird als eine (endliche) Anfragefolge modelliert, die ein Online-Algorithmus stückweise erhält. Nach dem Bekanntwerden einer Anfrage muss der Online-Algorithmus eine Entscheidung über seine weitere Arbeitsweise treffen, ohne die zukünftige Anfragen zu kennen. Die Entscheidungen des Online-Algorithmus sind je nach Problem eventuell zusätzlichen Einschränkungen unterworfen.
Zahlreiche Problemstellungen besitzen in natürlicher Weise Online-Charakter. Wir möchten in diesem Projekt Grundlagenforschung für die Konstruktion und die Analyse von Online-Algorithmen betreiben. Ziel ist es, den übermäßigen Pessimismus der klassischen kompetitiven Analyse (dem "Standard-Mittel" zur theoretischen Beurteilung von Online-Algorithmen) teilweise zu beheben und aussagekräftigere Beurteilungen für Algorithmen herzuleiten. Dabei stehen drei Themengebiete im Vordergrund:
- die Analyse von randomisierten Algorithmen (der Zufall hilft beim Entwurf von Algorithmen)
- die Analyse von Algorithmen bei zufälliger Eingabe (der Zufall hilft bei der Analyse des "typischen" Verhaltens von Algorithmen)
- die Analyse von Algorithmen bei strukturell beschränkter Eingabe
Unsere Konzepte sollen anhand von drei elementaren Online-Problemen entwickelt und verifiziert werden, dem Bincoloring-Problem (aus dem Online Commissioning-Vehicle-Problem extrahiert); dem Dial-a-Ride-Problem und Pfadfärbungsproblemen in Graphen.
Projekt 3: Evolution und Phasenübergänge
Üblicherweise besagt ein mathematischer Satz, dass alle Elemente einer festgelegten Klasse eine bestimmte Eigenschaft haben. Im Gegensatz dazu hat dieses Projekt die Charakterisierung zufälliger Objekte als zentrales Thema. Gemeint ist hiermit die Suche nach strukturellen Eigenschaften, die ein zufällig aus einer Klasse ausgewähltes Element mit hoher Wahrscheinlichkeit hat.
Die Beantwortung der Leitfrage 1 und der durch sie charakterisierten Fragestellungen dieses Projekts ist in vielen Fällen die Grundvoraussetzung für eine probabilistische Analyse eines Algorithmus (siehe Leitfrage 3). Eine solche Analyse, bei der die Leistung des Algorithmus an einer (gemäß einer stochastischen Verteilung) zufällig ausgewählten Instanz gemessen wird, beruht auf den Eigenschaften eines typischen Elements des Suchraums und ein vollständiges Bild dieser typischen Struktureigenschaften wiederum ergibt sich häufig erst dann, wenn die Evolution der zugrunde liegenden Klasse geklärt ist.
Ein wesentlicher Bestandteil dieses Projekts besteht in der Untersuchung der Evolution von Gn,p. Der Evolutionsaspekt besteht darin, dass man wissen möchte, wie sich typische Eigenschaften von Gn,p mit wachsender Kantenwahrscheinlichkeit p verändern. Für viele Parameter ist das Evolutionsverhalten inzwischen geklärt. Für "komplexe" Parameter wie die listenchromatische Zahl oder die Theta-Funktion sind wesentliche Fragen noch offen. Neuere Hilfsmittel wie z.B. die Talagrand-Ungleichung haben allerdings in jüngster Zeit erhebliche Fortschritte ermöglicht.
Erheblich weniger weiß man bisher über die Evolution von zufälligen Graphen mit Nebenbedigungen. In diesem Projekt werden drei verschiedene Nebenbedingungen betrachtet,
- zufällige Graphen mit verbotenen Teilgraphen,
- zufällige planare Graphen und
- sogenannte "kleine Welt"-Netzwerke.
Ein wesentliches Ziel bei der Untersuchung solcher Netzwerke ist die Charakterisierung (im Sinne von Leitfrage 2) von komplexen Netzwerken durch geeignete Zufallsmodelle.
Projekt 4: Zufall bei Entwurf und Analyse von diskreten Algorithmen
Für eine Reihe bekannter kominatorischer Optimierungsprobleme, etwa Graphenfärbungsproblem, das Stabile-Menge-Problem in Graphen oder das MAX k-SAT-Problem, sind Nichtapproximierbarkeitsresultate bekannt. Unter gewissen komplexitätstheoretischen Annahmen lassen diese Probleme also keine polynomiellen Algorithmen zu, die auf jeder Instanz eine optimale Lösung bzw. eine gute Approximationslösung berechnen. Daher fragte bereits Karp nach
- Heuristiken, die auf fast jeder Instanz eine gute Lösung des Optimierungsproblems bestimmen, und auf jeder Eingabe polynomielle Laufzeit haben, sowie nach
- Algorithmen, die auf jeder Eingabe eine akzeptable Approximationsgüte garantieren, und deren erwartete Laufzeit polynomiell ist,
und gab damit den Anstoß zur probabilistischen Analyse von Algorithmen. Im Sinne von Leitfrage 3 befassen wir uns in diesem Projekt mit fundamentalen kombinatorischen Problemen wie Graphenfärbung, Finden einer größten stabilen Menge oder dem Erfüllbarkeitsproblem.
Neben der probabilistischen Analyse soll in diesem Projekt der Zufall auch als algorithmisches Konzept studiert werden. Im Sinne von Leitfrage 4 lautet die Zielsetzung dann, durch Randomisierung verbesserte Algorithmen zu entwickeln.
Projekt 5: Geometrie und Kombinatorik von 0/1-Polytopen
Ein großer Teil der Erfolge in der Kombinatorischen Optimierung in den vergangenen Jahrzehnten beruht auf Einsichten in die Geometrie der zu verschiedenen kombinatorischen Problemen gehörenden Polytope. Ein solches Polytop ist in der Regel die konvexe Hülle der charakteristischen Vektoren der betrachteten kombinatorischen Objekte (z.B. die Kantenteilmengen eines Graphen, welche Matchings sind). Während so die Struktur zahlreicher Spezialklassen von 0/1-Polytopen (konvexe Hüllen von Punkten mit 0/1-Koordinaten) intensiv erforscht wurde, gibt es über die allgemeine Klasse der 0/1-Polytope bisher nur wenige Erkenntnisse.
In diesem Projekt wollen wir verschiedene strukturelle Fragestellungen über 0/1-Polytope untersuchen. Der Zufall kommt dabei zweifach ins Spiel: zum einen soll die Erforschung zufälliger 0/1-Polytope allgemeine Strukturerkenntnisse über die Klasse der 0/1-Polytope bringen, zum anderen sind manche der geplanten Strukturuntersuchungen relevant für randomisiert-algorithmische Fragestellungen über kombinatorische Objekte, wie z.B. die Frage nach dem zufälligen Erzeugen einer Basis eines gegebenen Matroids.
Projekt 6: Enumeration und zufälliges Erzeugen
Für viele endliche Klassen von kombinatorischen Objekten - als einfaches erstes Beispiel seien die aufspannenden Bäume in einem endlichen Graphen genannt - stellen sich in ganz verschiedenem Kontext vier (theoretisch wie methodisch) eng verwandte Probleme:
- erzeuge ein zufälliges Objekt/Beispiel,
- schätze die Anzahl der Objekte,
- bestimme die Anzahl der Objekte,
- erzeuge eine vollständige Liste der Objekte.
In diesem Projekt sollen solche Fragestellungen der Enumeration und des zufälligen Erzeugens in vier Anwendungsbereichen untersucht werden.
English