Name
Abstract | ||
|---|---|---|
In this paper, we consider the following red-blue median problem which is a generalization of the well-studied k-median problem. The input consists of a set of red facilities, a set of blue facilities, and a set of clients in a metric space and two integers k r ,k b ≥0. The problem is to open at most k r red facilities and at most k b blue facilities and minimize the sum of distances of clients to their respective closest open facilities. We show, somewhat surprisingly, that the following simple local search algorithm yields a constant factor approximation for this problem. Start by opening any k r red and k b blue facilities. While possible, decrease the cost of the solution by closing a pair of red and blue facilities and opening a pair of red and blue facilities. We also improve the approximation factor for the prize-collecting k-median problem from 4 (Charikar et al. in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pp. 642–641, 2001) to 3+ϵ, which matches the current best approximation factor for the k-median problem. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s00453-011-9547-9 | Algorithmica |
Keywords | Field | DocType |
Facility location,k,-median,Prize-collecting,Local search algorithms | Integer,Discrete mathematics,Combinatorics,Algorithm,Facility location problem,Metric space,Local search (optimization),Mathematics | Journal |
Volume | Issue | ISSN |
63 | 4 | 0178-4617 |
Citations | PageRank | References |
3 | 0.42 | 27 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| MohammadTaghi Hajiaghayi | 1 | 3082 | 201.38 |
| R. Khandekar | 2 | 17 | 1.41 |
| G. Kortsarz | 3 | 56 | 2.79 |