TY - GEN

T1 - A plant location guide for the unsure

AU - Anthony, Barbara M.

AU - Goyal, Vineet

AU - Gupta, Anupam

AU - Nagarajan, Viswanath

PY - 2008

Y1 - 2008

N2 - This paper studies an extension of the k-median problem where we are given a metric space (V, d) and not just one but m client sets {S i ⊆ V} m i=1, and the goal is to open k facilities F to minimize: max i∈[m] {Σ j∈S i d(j,F)}, i.e., the worst-case cost over all the client sets. This is a "min-max" or "robust" version of the k-median problem; however, note that in contrast to previous papers on robust/stochastic problems, we have only one stage of decision-making-where should we place the facilities? We present an O(log n + log m) approximation for robust k-median: The algorithm is combinatorial and very simple, and is based on reweighting/ Lagrangeanrelaxation ideas. In fact, we give a general framework for (minimization) facility location problems where there is a bound on the number of open facilities. For robust and stochastic versions of such location problems, we show that if the problem satisfies a certain "projection" property, essentially the same algorithm gives a logarithmic approximation ratio in both versions. We use our framework to give the first approximation algorithms for robust/stochastic versions of k-tree, capacitated k-median, and fault-tolerant k-median.

AB - This paper studies an extension of the k-median problem where we are given a metric space (V, d) and not just one but m client sets {S i ⊆ V} m i=1, and the goal is to open k facilities F to minimize: max i∈[m] {Σ j∈S i d(j,F)}, i.e., the worst-case cost over all the client sets. This is a "min-max" or "robust" version of the k-median problem; however, note that in contrast to previous papers on robust/stochastic problems, we have only one stage of decision-making-where should we place the facilities? We present an O(log n + log m) approximation for robust k-median: The algorithm is combinatorial and very simple, and is based on reweighting/ Lagrangeanrelaxation ideas. In fact, we give a general framework for (minimization) facility location problems where there is a bound on the number of open facilities. For robust and stochastic versions of such location problems, we show that if the problem satisfies a certain "projection" property, essentially the same algorithm gives a logarithmic approximation ratio in both versions. We use our framework to give the first approximation algorithms for robust/stochastic versions of k-tree, capacitated k-median, and fault-tolerant k-median.

UR - http://www.scopus.com/inward/record.url?scp=58449107422&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449107422&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449107422

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1164

EP - 1173

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -