Friday, October 19, 10:50am, CSE 3941
Title: Max-Min Facility Location and Set Coverage Problems
Speaker: Anupam Gupta, Carnegie Mellon University
Abstract:
Consider the following problem: you want to locate k facilities to
serve some set of demands arriving tomorrow. Unfortunately, you do
not precisely know what the demand set will be --- you merely know
that it will be one of M potential demand sets {S_1,..., S_M} given
to you in advance, and that the actual demand set S_i will be chosen
from these M sets by an adversary after seeing your solution.
Where should you place your facilities?
We consider the problems of locating these k facilities to minimize
the worst-case cost suffered, or to maximize the worst-case profit
collected, and give greedy-style algorithms for several such problems.
This is based on work with Barbara Anthony, Vineet Goyal, Carlos
Guestrin, Andreas Krause, Viswanath Nagarajan (all at Carnegie
Mellon University), and Brendan MacMahan (at Google, Pittsburgh).