Überdeckungsbasierte Standortprobleme für Baumgraphen
10.12.2010Standortprobleme beschäftigen sich mit der Auswahl von Standorten für neu zu eröffnende Versorger. Auf der Konferenz ISAAC'10 stellt Joachim Spoerhase einen optimalen Algorithmus für ein überdeckungsbasiertes Standortproblem auf Baumgraphen vor.
Das Problem fragt nach einem Standort, von dem aus möglichst viele Kunden in einem vorgegebenem Netzwerk bedient werden können. Ein Kunde kann hierbei bedient werden, wenn sein Abstand zum Versorger eine vorgegebene Schranke nicht überschreitet. Joachim Spoerhase entwickelt einen Algorithmus, der dieses Problem in O(n log n) Zeit auf Baumgraphen löst. Dieser Algorithmus ist schneller als die bisherigen Ansätze: O(n2) (Meggiddo et al., 83), O(n log2n) (Tamir et al., 96) und O(n log2 n/log log n) (Spoerhase, Wirth, 09). Joachim Spoerhase weist darüberhinaus nach, dass diese Laufzeit (für bestimmte Berechenbarkeitsmodelle) sogar bestmöglich ist.
