ICS Theory Group

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.