Approximationalgorithmen für kombinatorische Optimierungsprobleme mit Packungsconstraints

• Antragsteller: Dr. Joachim Spoerhase
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 399223600

Die Aufgabe eine optimale Lösung für ein gegebenes (diskretes) Problem zu ermitteln ist allgegenwärtig in der Informatik und wird gewöhnlich als kombinatorisches Optimierungsproblem bezeichnet. Viele der natürlicherweise auftretenden Probleme sind NP-schwer, was die Existenz eines polynomiellen Algorithmus, der ein solches Problem optimal löst, unwahrscheinlich macht. Eine natürliche Herangehensweise für NP-schwere Optimierungsprobleme ist die Entwicklung von Approximationsalgorithmen, die in polynomieller Zeit eine approximative, aber nicht notwendigerweise optimale Lösung berechnen. Im Bereich der Approximationsalgorithmen wurde eine Vielzahl algorithmischer Techniken entwickelt. Und obwohl das Gebiet mittlerweile relativ ausgereift ist, sind viele interessante und fundamentale Fragen weiterhin offen.Beispielsweise versteht man derzeit noch nicht zufriedenstellend, wie das Hinzufügen eines (scheinbar) einfachen Constraints wie z.B. einem Kapazitätsconstraint (oder allgemeiner einem Packungsconstraint) die Approximierbarkeit des Problems beeinflusst. Für viele fundamentale Probleme (wie z.B. Facility-Location oder k-Median) ist die grundlegende Version fast vollständig oder zumindest zufriedenstellend erforscht. Viele existierende Algorithmen basieren auf einer engen Verbindung zu einer kontinuierlichen Relaxierung des Problems. Diese Relaxierungen haben jedoch oft eine unbeschränkte Ganzzahligkeitslücke, wenn man einen der oben genannten Constraints hinzufügt. Auch die Lücke zwischen den besten bekannten oberen und unteren Approximierbarkeitsschranken ist oft groß trotz signifikanter Bemühungen durch die Forschungsgemeinschaft.In diesem Projekt wollen wir die Approximierbarkeit verschiedener fundamentaler Optimierungsprobleme unter Anwesenheit von Packungsconstraints untersuchen. Für einige dieser Probleme würde jeglicher nennenswerte Fortschritt von der Forschungsgemeinschaft wohl als Durchbruch betrachtet werden. In anderen Fällen glauben wir, dass neue Resultate einen wertvollen Beitrag zu einem systematischeren Verständnis für die Anwesenheit solcher Constraints darstellen würde. Wir werden uns auf die Untersuchung der Effektivität kürzlich entwickelter algorithmischer Werkzeuge (wie z.B. beim Runden von erweiterten LP-Formulierungen oder bei der Optimierung submodularer Funktionen) auf die betrachteten Probleme konzentrieren.Im Einzelnen werden wir uns mit kapazitierten Standortproblemen, kapazitierten oder kardinalitätsbeschränkten Überdeckungsproblemen und Netzwerkdesign-Problemen mit Distanzconstraints (als speziellem Packungsconstraint) beschäftigen. Wir werden uns auch mit Varianten auseinandersetzen, bei denen die Verletzung eines Constraints nicht verboten ist aber in der Zielfunktion bestraft wird (weiche Constraints).

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Finnland, Polen
• Kooperationspartner: Dr. Jaroslaw Byrka; Professor Parinya Chalermsook, Ph.D.; Professor Dr. Markus Chimani