# ICS 269, Spring 2002: Theory Seminar

## 31 May 2002:

Title: Online Facility Location,
by Adam Meyerson.
IEEE Symposium on Foundations of Computer Science (FOCS) 2001.

Speaker: Matthew Ba Nguyen

Abstract:
The author considers the online version of the facility location problem
where demand points arrive one at a time and facilities must be opened to
mantain them. The author presents an O(log n)-competitive algorithm and
shows that no algorithm can be O(1)-competitive. Also, an
O(1)-competitive algorithm is presented when the power of the adversary is
reduced such that each demand point arrives in a random order.