The Online Median Problem \Lambda

Abstract We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the on-line median problem. Whereas the k-median problem involves optimizing the simultaneous placementof k facilities, the online median problem imposes the following additional constraints: the facilities areplaced one at a time; a facility, once placed, cannot be moved; the total number of facilities to be placed, k, is not known in advance. The objective of an online median algorithm is to minimize competitiveratio, 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. Inaddition, 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 spiritto the recent primal-dual-based facility location algorithm of Jain and Vazirani, but our approach is more elementary and yields an improved running time