Enumeration und zufälliges Erzeugen

• Antragsteller: Professor Dr. Volker Kaibel, seit 10/2006
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2001 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 413: Algorithmen, Struktur, Zufall
• Ehemaliger Antragsteller: Professor Dr. Günter M. Ziegler, bis 10/2006