Deutsch Intern
    Chair of Computer Science I - Algorithms and Complexity

    Maximum Coverage Location on Tree Graphs


    Location problems deal with the choice of locations for facilities that are to be opened. At the conference ISAAC'10, Joachim Spoerhase presents an optimal algorithm for the so-called single maximum coverage location problem on tree-graphs.

    The problem asks for a location that allows a facility to serve the maximum number of customers in a given network. Here, a customer is served if her distance to the facility does not exceed a given bound. Joachim Spoerhase develops an algorithm that solves this problem in O(n log n) time on tree graphs. This algorithm is faster than the previous approaches: O(n2) (Meggiddo et al., 83), O(n log2n) (Tamir et al., 96) and O(n log2 n/ log log n) (Spoerhase and Wirth, 09). Moreover, Joachim Spoerhase proves that this running time is best possible (for certain models of computation).