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).