Please use this identifier to cite or link to this item:

Online maintenance of k-medians and k-covers on a line

Authors Fleischer, R. HKUST affiliated (currently or previously)
Golin, M.J. View this author's profile
Zhang, Y. HKUST affiliated (currently or previously)
Issue Date 2006
Source Algorithmica , v. 45, (4), 2006, p. 549-567
Summary The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(kn2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality or properties of totally monotone matrices, can reduce this to O(kn) time. However, these speed-up techniques are inherently static and cannot be used in an online setting, i.e., if we want to increase the size of the problem by one new point. Then, in the worst case, we could do no better than recalculating the solution to the entire problem from scratch in O(kn) time. The major result of this paper is to show that we can maintain the dynamic programming speed up in an online setting where points are added from left to right on a line. Computing the new k-medians after adding a new point takes only O(k) amortized time and O(k log n) worst-case time (simultaneously). Using similar techniques, we can also solve the online k-coverage with uniform coverage on a line problem with the same time bounds. © 2006 Springer Science+Business Media, Inc.
ISSN 0178-4617
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science