  In this paper, we provide a rigorous theoretical investigation of an online
learning version of the Facility Location problem which is motivated by
emerging problems in real-world applications. In our formulation, we are given
a set of sites and an online sequence of user requests. At each trial, the
learner selects a subset of sites and then incurs a cost for each selected site
and an additional cost which is the price of the user's connection to the
nearest site in the selected subset. The problem may be solved by an
application of the well-known Hedge algorithm. This would, however, require
time and space exponential in the number of the given sites, which motivates
our design of a novel quasi-linear time algorithm for this problem, with good
theoretical guarantees on its performance.
