Facility location on graphs

Hartmann, Tim Adrian; Rossmanith, Peter (Thesis advisor); Marx, Dániel (Thesis advisor)

Aachen : RWTH Aachen University (2022, 2023)
Doktorarbeit

Dissertation, RWTH Aachen University, 2022

Kurzfassung

Wir betrachten zwei nah verwandte Facility-Location-Probleme auf Graphen, deren Kanten einheitliche Länge haben und wo Facilities auch innerhalb einer Kante platziert werden können. Das Ziel bei delta-Zerstreuung ist, so viele Facilities wie möglich zu platzieren, unter der Bedingung, dass jede zwei Facillities mindestens delta weit auseinanderliegen. Das Ziel bei delta-Abdeckung ist die Abdeckung des ganzen Graphen mit der minimalen Anzahl an Facilities; das heißt, wir wollen so wenige Facilities wie möglich setzen, unter der Bedingung, dass jeder Punkt auf jeder Kante des Graphen höchsten delta weit weg ist von einer Facility. Wir untersuchen die algorithmische Komplexität dieser beiden Probleme für alle reellen Distanzen delta. Für rationale delta mit Zähler 1 ist delta-Abdeckung is in polynomieller Zeit lösbar, während es NP-schwer ist für alle anderen delta. Ähnlich ist delta-Zerstreuung für rationale delta mit Zähler 1 oder 2 in polynomieller Zeit lösbar, während es NP-schwer ist für alle anderen delta. In der Tat sind 1-Abdeckung und 2-Zerstreuung duale Probleme in der Art, wie die Probleme Knotenüberdeckung und Stabile Menge dual sind, wie wir zeigen. Wir erforschen die Komplexität der beiden Probleme mit der Lösungsgröße k als Parameter. Wir bestimmen die parametrisierte Komplexität für jedes reelle delta. Die Komplexität von delta-Zerstreuung springt von FPT zu W[1]-schwer beim Wert von 2. Ähnlich bildet 3/2 für delta-Abdeckung einen Schwellwert, wo die Komplexität von FPT zu W[2]-schwer springt. Außerdem betrachten wir delta-Zerstreuung unter Parametern, welche die Komplexität des Eingabegraphen messen, wie zum Beispiel Baumweite und Baumtiefe. Wir leiten einige algorithmische Resultate ab mittels zwei zentraler technischer Werkzeuge für delta-zerstreute Mengen, welche eine Verbindung zu einem verallgemeinertem Stabile-Menge-Problem erlauben. Das erste Werkzeug verknüpft ein optimale delta-zerstreute Menge mit einer optimalen delta/(delta+1)-zerstreuten Menge für delta <= 3 (und ähnlich für delta-Abdeckung). Das zweite Werkzeug ist eine konstruktives Rundungs-Verfahren. Es transformiert eine delta-zerstreute Menge S in eine delta*-zerstreute Menge S*, wobei delta* eine leicht größere rationale Zahl mit kleinem Nenner und Zähler ist. Abschließend und als ein Beispiel, das nicht auf unserem Rundungs-Verfahren basiert, entwickeln wir einen FPT-Algorithmus für delta-Zerstreuung mit Nachbarschafts-Vielfalt als Parameter.

Einrichtungen

• Fachgruppe Informatik [120000]
• Lehr- und Forschungsgebiet Theoretische Informatik [121220]