Advertisement
Published in:
2010 | OriginalPaper | Chapter
An Optimal Algorithm for Single Maximum Coverage Location on Trees and Related Problems
Author : Joachim Spoerhase
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 Ω(
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.