Zentralprojekt

• Applicant: Professor Dr. Mathias Schacht, since 10/2007
• Subject Area: Mathematics
• Term: from 2001 to 2009
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Units
• Subproject of: FOR 413: Algorithms, Structure, Randomness
• Ehemaliger Antragsteller: Professor Dr. Hans Jürgen Prömel, until 10/2007