Title: A Plant Location Guide for the Unsure Speaker: Barbara Anthony, Carnegie-Mellon University Date/Time: February 13, 2008 at 9:00 - 10:00am (MST) Location: CSRI Bldg/Room 90 Sandia NM and videoconferenced to Brief Abstract: The k-median problem has been a central and well-studied problem of interest in approximation algorithms and operations research: given a set S of clients in a metric space, open a set of k facilities F so that the total distance of the clients to the open facilities is minimized. We study the "robust" version of the k-median problem where we are given not just one but m client sets, and the goal is to open k facilities to minimize the worst-case cost over all the client sets. The problem arises naturally, for example, when we have a demand set for each day of the week, and would like to open k facilities so that we do well on any given day. We present an O(log n + log m) approximation for robust k-median, the first non-trivial approximation algorithm known for this problem. In fact, we obtain a general framework for (minimization) facility location problems where we are allowed to open just k 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. CSRI POC: Scott Collis, (1416) 284-1123 and Patty Hough, (8962) 925 294-1518 |