Efficient Algorithms for One-Dimensional k-Center Problems

Danny Z. Chen, Jian Li, Haitao Wang

We consider the problem of finding k centers for n weighted points on a real line. This (weighted) k-center problem was solved in O(n log n) time previously by using Cole's paramet…