The Online Median Problem

Ramgopal R. Mettu and C. Greg Plaxton

We introduce a natural variant of the (metric uncapacitated)
$k$-median problem that we call the \emph{online median problem}.
Whereas the $k$-median problem involves optimizing the simultaneous
placement of $k$ facilities, the online median problem imposes the
following additional constraints: the facilities are placed one at a
time; a facility cannot be moved once it is placed, and the total
number of facilities to be placed, $k$, is not known in advance.  The
objective of an online median algorithm is to minimize the competitive
ration, that is, the worst-case ratio of the cost of an online
placement to that of an optimal offline placement.  Our main result is
a linear-time constant-competitive algorithm for the online median
problem.  In addition, we present a related, though substantially
simpler, linear-time constant-factor approximation algorithm for the
(metric uncapacitated) facility location problem.  The latter
algorithm is similar in spirit to the recent primal-dual-based
facility location algorithm of Jain and Vazirani, but our approach is
more elementary and yields an improved running time.