Computer Science – Data Structures and Algorithms
Scientific paper
2010-02-02
Computer Science
Data Structures and Algorithms
10 pages, 1 figure
Scientific paper
We consider the indirect covering subtree problem (Kim et al., 1996). The input is an edge weighted tree graph along with customers located at the nodes. Each customer is associated with a radius and a penalty. The goal is to locate a tree-shaped facility such that the sum of setup and penalty cost is minimized. The setup cost equals the sum of edge lengths taken by the facility and the penalty cost is the sum of penalties of all customers whose distance to the facility exceeds their radius. The indirect covering subtree problem generalizes the single maximum coverage location problem on trees where the facility is a node rather than a subtree. Indirect covering subtree can be solved in $O(n\log^2 n)$ time (Kim et al., 1996). A slightly faster algorithm for single maximum coverage location with a running time of $O(n\log^2n/\log\log n)$ has been provided (Spoerhase and Wirth, 2009). We achieve time $O(n\log n)$ for indirect covering subtree thereby providing the fastest known algorithm for both problems. Our result implies also faster algorithms for competitive location problems such as $(1,X)$-medianoid and $(1,p)$-centroid on trees. We complement our result by a lower bound of $\Omega(n\log n)$ for single maximum coverage location and $(1,X)$-medianoid on a real-number RAM model showing that our algorithm is optimal in running time.
No associations
LandOfFree
An Optimal Algorithm for the Indirect Covering Subtree Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Optimal Algorithm for the Indirect Covering Subtree Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Optimal Algorithm for the Indirect Covering Subtree Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-600632