Approximationsalgorithmen für geometrische Optimierungsprobleme

Abstract

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.