Zentralprojekt

• Antragsteller: Professor Dr. Mathias Schacht, seit 10/2007
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2001 bis 2009
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5467699

Das Thema der Forschergruppe ist der Einfluss des Zufalls auf das klassische Zusammenspiel von Struktureinsichten und Algorithmenanalyse in der Diskreten Mathematik. Der algorithmische Fokus liegt dabei auf kombinatorischen Optimierungsproblemen und entsprechend stehen Graphen, Polytope und aussagenlogische Formeln als Forschungsgegenstände von Strukturuntersuchungen im Vordergrund. Die Auswirkungen des Zufalls werden dabei unter verschiedenen Aspekten erforscht. Einsichten in typische Struktureigenschaften zufälliger Objekte bilden die Grundlage für die Average-Case-Analysen von Algorithmen. Randomisierte Verfahren nutzen den Zufall, um ihre Entscheidungen vor komplexitätstheoretischen Gegenspielern zu verbergen. Sie werden sowohl bei Fragen der Optimierung als auch für probabilistische Konstruktionen und zufälliges Erzeugen verwendet. Der Zufall ist daher relevant für Strukturuntersuchungen und für die Erforschung von Algorithmen, insbesondere an der Schnittstelle der beiden Bereiche. Er ist gleichermaßen Forschungsgegenstand wie Untersuchungsmethode. Die Forschergruppe bündelt die Erfahrungen und Kompetenzen der beteiligten Arbeitsgruppen und bildet ein naheszu ideales Forum, um die zahlreichen inhaltlichen Verflechtungen zwischen den Projekten in dem Spannungfeld von Algorithmen, Struktur und Zufall zu bearbeiten.

• DFG-Verfahren: Forschungsgruppen
• Teilprojekt zu: FOR 413: Algorithmen, Struktur, Zufall
• Ehemaliger Antragsteller: Professor Dr. Hans Jürgen Prömel, bis 10/2007