Dynamische und sublineare Algorithmen für lokale Probleme

Groß angelegte Datenanwendungen in der Praxis haben zur Entstehung von Berechnungsmodellen wie dynamisch und sublinear geführt, die sich auf die Pflege von Datenstrukturen über sich entwickelnde Datensätze und die Lösung von Optimierungsproblemen konzentrieren, ohne auf den Großteil der zugrunde liegenden Daten zuzugreifen. Optimierungsprobleme, die mehr lokale Garantien für die Eingabe erfordern, scheinen in diesen Modellen effiziente Algorithmen zuzulassen. Dieses Projekt zielt darauf ab, Algorithmusentwurfstechniken für dynamische und sublineare Modelle einzuführen und Prinzipien zu erforschen, die effiziente Algorithmen in beiden Modellen ermöglichen. Insbesondere wird diese Richtung im Kontext grundlegender lokaler Optimierungsprobleme erforscht, darunter das approximative Maximum-Matching-Problem und das Graphenkantenfärbeproblem sowie deren Verallgemeinerungen. Das Maximum-Matching-Problem zielt darauf ab, die größtmögliche Übereinstimmung in einem Graphen zu finden. Das Problem ist seit jeher ein Eckpfeiler der kombinatorischen Optimierungsforschung und hat eine breite Palette praktischer Anwendungen, wie z. B. die Zuweisung von Aufträgen, die Gestaltung von Netzwerken, die Zuweisung von Ressourcen, die Routenplanung von Fahrzeugen und die Zeitplanung, um nur einige zu nennen. Beim verwandten Kantenfärbungsproblem geht es darum, die Kanten eines Graphen in eine kleine Anzahl von Übereinstimmungen zu unterteilen. Es findet Anwendung in der Terminplanung, der Telekommunikation, bei Zuordnungsproblemen und der Parallelverarbeitung. Beide Probleme (insbesondere ihre Näherungsversionen) können als lokale Probleme in dem Sinne beschrieben werden, dass wir Eigenschaften für die unmittelbare Nachbarschaft von Knoten definieren können, die, wenn sie erfüllt sind, gültige Ausgaben definieren. Aus intuitiven Gründen scheinen lokale Probleme effiziente dynamische und sublineare Algorithmen zuzulassen. Ein dynamischer Algorithmus, der mit sich verändernden Eingaben arbeitet, kann seine Ausgabe schneller anpassen, wenn die Auswirkungen der Änderungen lokal sind. Sublineare Algorithmen können lokal Teile der Ausgabe berechnen, aus denen sie Statistiken für die gesamten Daten ableiten können. Dieses Projekt zielt darauf ab, seit langem bestehende offene Probleme in Bezug auf die Anpassung und die Kantenfärbung und ihre Verallgemeinerungen in dynamischen und sublinearen Modellen zu lösen. Um dieses Ziel zu erreichen, wird es sich auf die Definition von Algorithmusentwurfstechniken konzentrieren, die in großem Umfang auf lokale Optimierungsprobleme angewandt werden können und zu Algorithmen führen, die in mehreren Berechnungsmodellen implementiert werden können.