Title: Approximation Algorithms for Network Design With Uncertainty
Speaker: Barbara Anthony
When: Wednesday, April 16, 10:30 am
Where: Doherty Hall 4303
Abstract: We present 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 (subsets of V) for i = 1, …, m, and the goal is to open k facilities F to minimize the worst-case cost over all the client sets, i.e. max_{i in [m]} sum_{j in S_i} d(j,F). 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 simple and combinatorial, and is based on reweighting/Lagrangean-relaxation 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.
This talk, on robust and stochastic location problems, covers one part of my thesis on approximation algorithms for network design with uncertainty.
Thesis Committee:
Anupam Gupta (Computer Science, chair)
Thomas Bohman (Math)
Alan Frieze (Math)
R. Ravi (Tepper)
