Approximate clustering via core-sets
From MaRDI portal
Publication:3579227
DOI10.1145/509907.509947zbMath1192.68871OpenAlexW2059651397MaRDI QIDQ3579227
Mihai Bădoiu, Sariel Har-Peled, Piotr Indyk
Publication date: 5 August 2010
Published in: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/509907.509947
Related Items (63)
Algorithm 1024: Spherical Triangle Algorithm: A Fast Oracle for Convex Hull Membership Queries ⋮ Linear-size universal discretization of geometric center-based problems in fixed dimensions ⋮ Topographic Mapping of Large Dissimilarity Data Sets ⋮ Dynamic coresets ⋮ An efficient inexact Newton-CG algorithm for the smallest enclosing ball problem of large dimensions ⋮ A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems ⋮ On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids ⋮ New algorithms for \(k\)-center and extensions ⋮ Clustering through continuous facility location problems ⋮ THE SMALLEST ENCLOSING BALL OF BALLS: COMBINATORIAL STRUCTURE AND ALGORITHMS ⋮ Fixed-parameter tractability and lower bounds for stabbing problems ⋮ Streaming and dynamic algorithms for minimum enclosing balls in high dimensions ⋮ On the \(k\)-means/median cost function ⋮ Streaming with minimum space: an algorithm for covering by two congruent balls ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ Some results on approximate 1-median selection in metric spaces ⋮ No dimension-independent core-sets for containment under homothetics ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ Random Projection and Recovery for High Dimensional Optimization with Arbitrary Outliers ⋮ On the string consensus problem and the Manhattan sequence consensus problem ⋮ The 2-center problem in three dimensions ⋮ Faster algorithms for the constrained \(k\)-means problem ⋮ Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams ⋮ The maximum vector-angular margin classifier and its fast training on large datasets using a core vector machine ⋮ Parameterized low-rank binary matrix approximation ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Analysis of agglomerative clustering ⋮ Efficient subspace approximation algorithms ⋮ 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 ⋮ A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems ⋮ Parameterized Low-Rank Binary Matrix Approximation ⋮ Metric \(k\)-median clustering in insertion-only streams ⋮ Improved linear embeddings via Lagrange duality ⋮ One-dimensional \(k\)-center on uncertain data ⋮ Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension ⋮ Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere ⋮ FRSDE: Fast reduced set density estimator using minimal enclosing ball approximation ⋮ Analysis of incomplete data and an intrinsic-dimension Helly theorem ⋮ Optimal core-sets for balls ⋮ Minimal containment under homothetics: a simple cutting plane approach ⋮ Small space representations for metric min-sum \(k\)-clustering and their applications ⋮ Faster balanced clusterings in high dimension ⋮ Frequency-based views to pattern collections ⋮ Faster core-set constructions and data-stream algorithms in fixed dimensions ⋮ Approximating global optimum for probabilistic truth discovery ⋮ Efficient approximation algorithms for clustering point-sets ⋮ Data Exploration by Representative Region Selection: Axioms and Convergence ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ A dual simplex-type algorithm for the smallest enclosing ball of balls ⋮ Approximate minimum enclosing balls in high dimensions using core-sets ⋮ Greedy Strategy Works for k-Center Clustering with Outliers and Coreset Construction ⋮ Some Estimates on the Discretization of Geometric Center-Based Problems in High Dimensions ⋮ A unified framework for clustering constrained data without locality property ⋮ Probabilistic smallest enclosing ball in high dimensions via subgradient sampling ⋮ Sublinear‐time approximation algorithms for clustering via random sampling ⋮ Uncertainty quantification of the 4th kind; optimal posterior accuracy-uncertainty tradeoff with the minimum enclosing ball ⋮ New Algorithms for k-Center and Extensions ⋮ Unnamed Item ⋮ Probabilistic \(k\)-median clustering in data streams ⋮ Streaming algorithms for extent problems in high dimensions ⋮ Minimum-volume enclosing ellipsoids and core sets ⋮ Approximation and complexity of the capacitated geometric median problem
This page was built for publication: Approximate clustering via core-sets
