An O(n2(logn)/loglogn) algorithm for the single maximum coverage location or the (1,Xp)-medianoid problem on trees

The single maximum coverage location problem on a tree consists of placing one facility onto a node such that the total weight of users covered by the facility is maximized. Users are located at nodes of the tree. Each user has an individual sensitivity radius and is covered if and only if the facility is placed within that radius. This problem is a generalization of the (1,Xp)-medianoid problem (Hakimi, 1990).We provide a recursive graph coarsening algorithm which improves the running time from O(n2) (Megiddo, 1983) to O(n2(logn)/loglogn).