Approximation schemes for clustering problems

DOI10.1145/780542.780550zbMath1192.68894OpenAlexW1970866964MaRDI QIDQ3581243

Kenyon Claire, Yuval Rabani, Marek Karpinski, Wenceslas Fernandez de la Vega

Publication date: 16 August 2010

Published in: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/780542.780550

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Related Items (25)

A refined approximation for Euclidean \(k\)-means ⋮ Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median ⋮ A framework for statistical clustering with constant time approximation algorithms for \(K\)-median and \(K\)-means clustering ⋮ Unnamed Item ⋮ Clustering through continuous facility location problems ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ A randomized PTAS for the minimum consensus clustering with a fixed number of clusters ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ The planar \(k\)-means problem is NP-hard ⋮ Data stability in clustering: a closer look ⋮ Line-Constrained k-Median, k-Means, and k-Center Problems in the Plane ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Approximation algorithms for min-sum \(k\)-clustering and balanced \(k\)-median ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Unnamed Item ⋮ Frequency-based views to pattern collections ⋮ Min sum clustering with penalties ⋮ Unnamed Item ⋮ The Planar k-Means Problem is NP-Hard ⋮ A unified framework for clustering constrained data without locality property ⋮ Center-based clustering under perturbation stability ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Sublinear‐time approximation algorithms for clustering via random sampling

This page was built for publication: Approximation schemes for clustering problems