Papers › Sets Clustering
Sets Clustering
Ibrahim Jubran, Murad Tukan, Alaa Maalouf, Dan Feldman
The input to the \emph{sets-k-means} problem is an integer k≥1 and a set 𝒫={P₁,⋯,Pₙ} of sets in ℝᵈ. The goal is to compute a set C of k centers (points) in ℝᵈ that minimizes the sum ∑_(P∈𝒫) min_(p∈P, c∈C) p-c ² of squared distances to these sets. An \emph{ε-core-set} for this problem is a weighted subset of 𝒫 that approximates this sum up to 1±ε factor, for \emph{every} set C of k centers in ℝᵈ. We prove that such a core-set of O(log²n) sets always exists, and can be computed in O(nlogn) time, for every input 𝒫 and every fixed d,k≥1 and ε∈(0,1). The result easily generalized for any metric space, distances to the power of z>0, and M-estimators that handle outliers. Applying an inefficient but optimal algorithm on this coreset allows us to obtain the first PTAS (1+ε approximation) for the sets-k-means problem that takes time near linear in n. This is the first result even for sets-mean on the plane (k=1, d=2). Open source code and experimental results for document classification and facility locations are also provided.
In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Tasks
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections