Enumeration und zufälliges Erzeugen

• Applicant: Professor Dr. Volker Kaibel, since 10/2006
• Subject Area: Mathematics
• Term: from 2001 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5467699

Das Erzeugen "zufälliger" Objekte einer gegebenen Klasse spielt in der Kombinatorik und in der Kombinatorischen Optimierung verschiedene Rollen mit zunehmender Bedeutung. Einerseits haben zufällige Objekte oft im Erwartungswert interessante Eigenschaften (darauf basiert etwa die berühmte Methode von Goemans & Williamson zum Finden von Schnitten garantiert hohen Gewichts in Graphen). Andererseits erlaubt die "zufällige Erzeugung" häufig die Exploration und das effiziente approximative Zählen von großen Mengen von Objekten, was mit determininistischen Algorithmen nachweislich sehr schwierig ist. Im geplanten Projekt sollen zwei fundamentale, komplementäre Verfahren bearbeitet, zusammengeführt und methodisch verbessert werden: das randomisierte Absteigen in einem Suchbaum, sowie Random Walks auf einem hochgradig zusammenhängenden Suchraum. Als "Benchmarks" haben wir uns vier fundamentale Probleme vorgenommen, auf denen wir unseren Fortschritt in Berechnung und Verständnis messen wollen: Ecken-Enumeration von Polyedern, abstrakte Zielfunktionen auf Polytopen, Triangulierungen des m x n-Gitters, und Determinanten von 0/1-Matrizen.

• DFG Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness
• Ehemaliger Antragsteller: Professor Dr. Günter M. Ziegler, until 10/2006