scientific article; zbMATH DE number 6789230

DOI10.4230/LIPIcs.SOCG.2015.754zbMath1378.68048arXiv1502.03316MaRDI QIDQ5368726

Pranjal Awasthi, Ali Kemal Sinop, Ravishankar Krishnaswamy, Moses Charikar

Publication date: 10 October 2017

Full work available at URL: https://arxiv.org/abs/1502.03316

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

vertex coverhardness of approximationEuclidean \(k\)-means

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (41)

A refined approximation for Euclidean \(k\)-means ⋮ Spectral concentration and greedy \(k\)-clustering ⋮ Minimization of Gini impurity: NP-completeness and approximation algorithm via connections with the \(k\)-means problem ⋮ Clustering through continuous facility location problems ⋮ Model assisted variable clustering: minimax-optimal recovery and algorithms ⋮ The provably good parallel seeding algorithms for the k‐means problem with penalties ⋮ Linear-time approximation scheme for \(k\)-means clustering of axis-parallel affine subspaces ⋮ The computational complexity of some explainable clustering problems ⋮ Improved PTAS for the constrained \(k\)-means problem ⋮ An LP-based \(k\)-means algorithm for balancing weighted point sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A semi brute-force search approach for (balanced) clustering ⋮ Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms ⋮ Unnamed Item ⋮ A constant FPT approximation algorithm for hard-capacitated \(k\)-means ⋮ Approximate Clustering with Same-Cluster Queries ⋮ A Streaming Algorithm for k-Means with Approximate Coreset ⋮ Polynomial time approximation schemes for clustering in low highway dimension graphs ⋮ 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 ⋮ On the cost of essentially fair clusterings ⋮ Noisy, Greedy and Not so Greedy k-Means++ ⋮ Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering ⋮ Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames ⋮ Improved and simplified inapproximability for \(k\)-means ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ Faster balanced clusterings in high dimension ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth and strong PCPs ⋮ The seeding algorithm for \(k\)-means problem with penalties ⋮ A unified framework for clustering constrained data without locality property ⋮ The seeding algorithms for spherical \(k\)-means clustering ⋮ Coresets for Fuzzy K-Means with Applications ⋮ Partial recovery bounds for clustering with the relaxed \(K\)-means ⋮ The bi-criteria seeding algorithms for two variants of \(k\)-means problem ⋮ An approximation algorithm for the uniform capacitated \(k\)-means problem ⋮ The seeding algorithm for spherical \(k\)-means clustering with penalties ⋮ Approximating dominating set on intersection graphs of rectangles and \(\mathsf{L}\)-frames ⋮ Unnamed Item

This page was built for publication: