A plant location guide for the unsure: Approximation algorithms for min-max location problems

Barbara Anthony, Vineet Goyal, Anupam Gupta, Viswanath Nagarajan

Research output: Contribution to journalArticlepeer-review


This paper studies an extension of the k-median problem under uncertain demand. We are given an n-vertex metric space (V, d) and m client sets {S i⊆V}i=1m. The goal is to open a set of k facilities F such that the worst-case connection cost over all the client sets is minimized, i.e min max, F⊆V, |F|=k i∈[m] {∑j∈Si d(j, F)}, where for any F ⊆ V, d(j, F) = minf∈F d(j, f). This is a "min-max" or "robust" version of the k-median problem. Note that in contrast to the recent papers on robust and stochastic problems, we have only one stage of decision-making where we select a set of k facilities to open. Once a set of open facilities is fixed, each client in the uncertain client-set connects to the closest open facility. We present a simple, combinatorial O(log n +log m)-approximation algorithm for the robust k-median problem that is based on reweighting/Lagrangean-relaxation ideas. In fact, we give a general framework for (minimization) k-facility location problems where there is a bound on the number of open facilities. We show that if the location problem satisfies a certain "projection" property, then both the robust and stochastic versions of the location problem admit approximation algorithms with logarithmic ratios. We use our framework to give the first approximation algorithms for robust and stochastic versions of several location problems such as k-tree, capacitated k-median, and fault-tolerant k-median.

Original languageEnglish (US)
Pages (from-to)79-101
Number of pages23
JournalMathematics of Operations Research
Issue number1
StatePublished - Feb 2010


  • Approximation algorithms
  • Facility location
  • Robust optimization
  • Stochastic optimization

ASJC Scopus subject areas

  • General Mathematics
  • Computer Science Applications
  • Management Science and Operations Research


Dive into the research topics of 'A plant location guide for the unsure: Approximation algorithms for min-max location problems'. Together they form a unique fingerprint.

Cite this