Debmalya Panigrahi

Online Non-Metric Facility Location and Related Problems

ABSTRACT:
The facility location problem consists of a set of n
clients, each of whom wants to be served by one among a set of
m facilities. Each client has a service cost for each facility,
in addition to each facility having a fixed setup cost for
serving a non-zero number of clients. (In the non-metric
version, the service costs can be arbitrary). The goal is to
minimize the total cost of the assignment of clients to
facilities. We consider the online version of this problem
where the clients arrive online, and each client needs to be
assigned to a facility immediately on arrival.

Alon et al (SODA 2004) gave a randomized O(\log m \log
n)-competitive algorithm for this problem. Our first result is
a derandomization of the above result when all the service
costs are known in advance; specifically, we obtain an O((\log
n + \log m)^2)-competitive deterministic algorithm for the
problem. We then use this algorithm to give an O((\log M + \log
N)^2)-competitive deterministic algorithm for the online
capacitated set cover problem, where M is the number of sets
and N is the number of elements. Finally, we give a reduction
of the online steiner tree problem with both node and edge
weights to the online non-metric facility location problem,
thereby yielding an O((\log N)^2)-competitive randomized
algorithm, where N is the number of nodes in the graph. We
leave the derandomization of this result as an open question.
No algorithm with polylogarithmic competitive ratio was known
previously for either of these problems.

The first two results are jointly with Yossi Azar and the last
result is with Seffi Naor and Mohit Singh.

BIO:
Debmalya Panigrahi is a PhD student in the Computer
Science and Artificial Intelligence Laboratory at MIT, where he
is advised by Prof. David Karger. His research interests are in
algorithms for combinatorial optimization, both for theoretical
and applied problems. Before coming to MIT, he received a
masters degree in Computer Science from the Indian Institute of
Science.