Kombinatorische Optimierungsprobleme auf Zufallsgraphen

Ein erheblicher Teil der Diskreten Mathematik und Theoretischen Informatik widmet sich der Entwicklung von Algorithmen zur effizienten Lösung kombinatorischer Optimierungsprobleme (Combinatorial Optimization Problems, COPs). Leider gibt es bei vielen wichtigen COPs `schwierige Instanzen`, die zeigen, dass Algorithmen nicht in der Lage sind, sie in polynomieller Zeit zu lösen, sofern P nicht gleich NP ist. Um die Komplexität dieser Probleme anzugehen, greifen Forscher oft auf eine Durchschnittsfallanalyse zurück. Die zugrunde liegende Philosophie der Durchschnittsfallanalyse besteht darin, dass Probleminstanzen aus der realen Welt im Allgemeinen nicht antagonistisch sind. Zum Beispiel kommen die Probleminstanzen, die man speziell konstruiert, um zu beweisen, dass ein Algorithmus in gewissen Fällen langsam ist, nicht oft vor. Daher verlagert sich das Ziel von der Entwicklung von Algorithmen, die alle möglichen Fälle effizient lösen, hin zur Entwicklung von Algorithmen, die für die am häufigsten auftretenden Fälle effektiv sind. Im Zusammenhang mit Graphproblemen bedeutet dies, dass diese Probleme im Bereich der Zufallsgraphen erforscht werden. Das Ziel dieses Projekts besteht darin, klassische COPs für dünn besetzte Zufallsgraphen, deren Verhalten nicht ausreichend erforscht ist zu untersuchen und dadurch Einblicke in ihr Verhalten und mögliche Lösungen in typischen Szenarien, die näher an der realen Welt liegen, zu bieten. COPs auf dünn besetzten Zufallsgraphen wurden auch in einer Vielzahl von Bereichen erforscht, darunter Probabilistische und Extremale Kombinatorik, Zufallsgraphentheorie, Theoretische Informatik und Statistische Physik.