Maximum Coverage Location on Tree Graphs
12/10/2010Location 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).
