Paper Info
Title
The Online Median Problem
Abstract
We introduce a natural variant of the (metric uncapacitated) k-median problem that we call the 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 ratio, 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 constant-competitive algorithm for the online median problem running in time that is linear in the input size. In addition, we present a related, though substantially simpler, constant-factor approximation algorithm for the (metric uncapacitated) facility location problem that runs in time linear in the input size. 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. While our primary focus is on problems which ask us to minimize the weighted average service distance to facilities, we also show that our results can be generalized to hold, to within constant factors, for more general objective functions. For example, we show that all of our approximation results hold, to within constant factors, for the k-means objective function.
Year
DOI
Venue
2000
10.1137/S0097539701383443
SIAM Journal on Computing
Keywords
DocType
Volume
optimal offline placement,k-median problem,constant factor,input size,k facility,linear-time constant-factor approximation algorithm,constant-competitive algorithm,online median algorithm,online median problem,on-line median problem,facility location problem,constant-factor approximation algorithm,online placement,median problem,linear-time constant-competitive algorithm,latter algorithm,computer science,polynomials,facility location,competitive ratio,linear approximation,approximation algorithms,linear time,cost function,approximation theory
Conference
32
Issue
ISSN
ISBN
3
0097-5397
0-7695-0850-2
Citations 
PageRank 
References 
88
8.10
14
Authors
2
Name
Order
Citations
PageRank
Ramgopal R. Mettu117722.23
C. Greg Plaxton21835281.07