piwik-script

English Intern
    Lehrstuhl für Informatik I - Algorithmen und Komplexität

    Überdeckungsbasierte Standortprobleme für Baumgraphen

    10.12.2010

    Standortprobleme 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.

    Überdeckungsbasiertes Standortproblem

    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.

    Zurück