Search Results

In k-clustering problems, we are given a metric space (𝒞, d), and must choose a set S of k centers to open. Each client j ∈ 𝒞 incurs an assignment cost, which is the distance between j and center in S that it has been assigned to. In this work, we study the minimum-norm k-clustering problem, where we are given an arbitrary monotone symmetric norm f, and wish to open k centers so as to minimize f(assignment-cost vector). This is a powerful generalization, encompassing many classical k-clustering problems including the k-median, k-means, and k-center problems. A simple and efficient algorithmic idea is that of adaptive sampling, wherein we randomly choose the location of the next center to open with probability proportional to its "cost" under the currently chosen set. While this has yielded fast algorithms for some k-clustering problem, little is known for settings without "min-sum" objectives. We devise the first adaptive-sampling-based bicriteria constant-factor approximation algorithm for general minimum-norm k-clustering, vastly expanding the scope of problems handled by adaptive sampling. For the special case of Top_ℓ norms, which form a building block of monotone symmetric norms, we show that adaptive sampling yields an O(log k)-approximation algorithm.