Linear-time approximation schemes for clustering problems in any dimensions
From MaRDI portal
Publication:3578186
DOI10.1145/1667053.1667054zbMath1327.68334OpenAlexW2155429109MaRDI QIDQ3578186
Amit Kumar, Yogish Sabharwal, Sandeep Sen
Publication date: 14 July 2010
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1667053.1667054
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Information storage and retrieval of data (68P20) Approximation algorithms (68W25) Randomized algorithms (68W20)
Related Items (46)
Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Unnamed Item ⋮ A lower bound for metric 1-median selection ⋮ Clustering through continuous facility location problems ⋮ On ultrametric 1-median selection ⋮ Better guarantees for \(k\)-median with service installation costs ⋮ Universal Algorithms for Clustering Problems ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ How to find a good explanation for clustering? ⋮ An efficient algorithm for the single facility location problem with polyhedral norms and disk-shaped demand regions ⋮ Some results on approximate 1-median selection in metric spaces ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ Deterministic metric 1-median selection with A \(1-o(1)\) fraction of points ignored ⋮ Parameterized low-rank binary matrix approximation ⋮ Data stability in clustering: a closer look ⋮ Approximate Clustering with Same-Cluster Queries ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Local Search Yields a PTAS for $k$-Means in Doubling Metrics ⋮ Local Search Yields Approximation Schemes for $k$-Means and $k$-Median in Euclidean and Minor-Free Metrics ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ On Las Vegas approximations for metric 1-median selection ⋮ A deterministic sublinear-time nonadaptive algorithm for metric 1-median selection ⋮ A unified framework of FPT approximation algorithms for clustering problems ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Attainable accuracy guarantee for the \(k\)-medians clustering in [0, 1] ⋮ Unnamed Item ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Clustering with Internal Connectedness ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ A unified framework for clustering constrained data without locality property ⋮ Learning the truth vector in high dimensions ⋮ Metric 1-Median Selection: Query Complexity vs. Approximation Ratio ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Unnamed Item ⋮ Lossy kernelization of same-size clustering ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Approximation and complexity of the capacitated geometric median problem
This page was built for publication: Linear-time approximation schemes for clustering problems in any dimensions
