The k-center and k-median problems are two central clustering techniques that are well-studied and widely used. In this paper, we focus on possible simultaneous generalizations of these two problems and present a bicriteria approximation algorithm for them with constant approximation factor in both dimensions. We also extend our results to the so-called incremental setting, where cluster centers are chosen one by one and the resulting solution must have the property that the first k cluster centers selected must simultaneously be near-optimal for all values of k.
展开▼
