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.

In the k-committee election problem, we wish to aggregate the preferences of n agents over a set of alternatives and select a committee of k alternatives that minimizes the cost incurred by the agents. While we typically assume that agent preferences are captured by a cardinal utility function, in many contexts we only have access to ordinal information, namely the agents' rankings over the outcomes. As preference rankings are not as expressive as cardinal utilities, a loss of efficiency is inevitable, and is quantified by the notion of distortion. We study the problem of electing a k-committee that minimizes the sum of the \ell-largest costs incurred by the agents, when agents and candidates are embedded in a metric space. This problem is called the \ell-centrum problem and captures both the utilitarian and egalitarian objectives. When k >= 2, it is not possible to compute a bounded-distortion committee using purely ordinal information. We develop the first algorithms (that we call mechanisms) for the \ell-centrum problem (when k >= 2), which achieve O(1)-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: O(log k log n) queries per agent, and O(k^2 log^2 n) queries in total (while achieving O(1)-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the \ell-centrum k-clustering problem.