Konferenzbeitrag
Approximationsalgorithmen für geometrische Optimierungsprobleme
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2021
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Gesellschaft für Informatik e.V.
Zusammenfassung
In diesem Beitrag betrachten wir verschiedene NP-schwere geometrische Optimierungs-probleme aus den Bereichen der konfliktfreien Färbung von Graphen, der kollisionsfreien Bewegungsplanung und der geometrischen Packung und Überdeckung, und fassen die Ergebnisse unserer Arbeit zusammen, die in [Ke20] ausführlich beschrieben werden. Neben anderen Ergebnissen präsentieren wir zu verschiedenen Problemvarianten aus diesen Problemfeldern Garantien, die den Faktor zwischen einer offensichtlichen Schranke an die optimale Lösung einer Instanz und dem tatsächlichen Wert einer optimalen Lösung beschränken. In vielen Fällen sind diese Garantien bestmöglich, was bedeutet dass es Familien von Instanzen gibt, für die der garantierte Faktor angenommen wird. Die konstruktiven Beweise für diese Garantien basieren auf Algorithmen, die sich in jedem Fall auch als effiziente Approximationsalgorithmen mit konstantem Approximationsfaktor interpretieren lassen.