Paper Info
Title
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems
Abstract
The single maximum coverage location problem is as follows. We are given an edge-weighted tree with customers located at the nodes. Each node u is associated with a demand w(u) and a radius r(u). The goal is to find, for some facility, a node x such that the total demand of customers u whose distance to x is at most r(u) is maximized. We give a simple O(n log n) algorithm for this problem which improves upon the previously fastest algorithms. We complement this result by an Omega(n log n) lower bound showing that our algorithm is optimal. We observe that our algorithm leads also to improved time bounds for several other location problems such as indirect covering subtree and certain competitive location problems. Finally, we outline how our algorithm can be extended to a large class of distance-based location problems.
Year
DOI
Venue
2010
10.1007/978-3-642-17517-6_39
ALGORITHMS AND COMPUTATION, PT I
Keywords
Field
DocType
graph algorithm,coverage,tree,efficient algorithm
Graph algorithms,Discrete mathematics,Combinatorics,Mathematics
Conference
Volume
ISSN
Citations 
6506
0302-9743
1
PageRank 
References 
Authors
0.35
10
1
Name
Order
Citations
PageRank
Joachim Spoerhase111214.12