The reverse greedy algorithm for the metric k-median problem

Details The reverse greedy algorithm for the metric k-median problem The reverse greedy algorithm for the metric k-median problem

2005-04-27

arxiv.org/abs/cs/0504104v2

Information Processing Letters 97:68-72(2006)

Computer Science

Data Structures and Algorithms

to appear in IPL. preliminary version in COCOON '05

Scientific paper

The Reverse Greedy algorithm (RGreedy) for the k-median problem works as follows. It starts by placing facilities on all nodes. At each step, it removes a facility to minimize the resulting total distance from the customers to the remaining facilities. It stops when k facilities remain. We prove that, if the distance function is metric, then the approximation ratio of RGreedy is between ?(log n/ log log n) and O(log n).

Affiliated with

Also associated with

No associations

Rating

The reverse greedy algorithm for the metric k-median 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 The reverse greedy algorithm for the metric k-median problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The reverse greedy algorithm for the metric k-median problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-612756