Faster balanced clusterings in high dimension
From MaRDI portal
Publication:2006774
DOI10.1016/j.tcs.2020.07.022zbMath1455.68274arXiv1809.00932OpenAlexW3045352063MaRDI QIDQ2006774
Publication date: 12 October 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1809.00932
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)
Related Items (5)
Improved parameterized approximation for balanced \(k\)-median ⋮ Shift of pairwise similarities for data clustering ⋮ FPT Approximation for Constrained Metric k-Median/Means ⋮ A unified framework for clustering constrained data without locality property ⋮ On parameterized approximation algorithms for balanced clustering
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The planar \(k\)-means problem is NP-hard
- Improved analysis of \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
- A simple \(D^2\)-sampling based PTAS for \(k\)-means and other clustering problems
- A local search approximation algorithm for \(k\)-means clustering
- Centrality of trees for capacitated \(k\)-center
- Clustering to minimize the maximum intercluster distance
- Cutting dense point sets in half
- An LP-based \(k\)-means algorithm for balancing weighted point sets
- Faster algorithms for the constrained \(k\)-means problem
- Capacitated center problems with two-sided bounds and outliers
- Approximating $k$-Median via Pseudo-Approximation
- Sublinear time algorithms for metric space problems
- Improved Approximation Guarantees for Lower-Bounded Facility Location
- Achieving anonymity via clustering
- Constant Factor Approximation for Capacitated k-Center with Outliers
- On the Complexity of Some Common Geometric Location Problems
- A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- On Coresets for k-Median and k-Means Clustering in Metric and Euclidean Spaces and Their Applications
- Linear-time approximation schemes for clustering problems in any dimensions
- Approximate clustering via core-sets
- A Best Possible Heuristic for the k-Center Problem
- How to Allocate Network Centers
- The Capacitated K-Center Problem
- Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
- Local Search Heuristics for k-Median and Facility Location Problems
- An Improved Approximation for k -Median and Positive Correlation in Budgeted Optimization
- On Uniform Capacitated k -Median Beyond the Natural LP Relaxation
- Improved Combinatorial Algorithms for Facility Location Problems
- A Unified Framework for Clustering Constrained Data without Locality Property
- k-means requires exponentially many iterations even in the plane
- A unified framework for approximating and clustering data
- Max flows in O(nm) time, or better
This page was built for publication: Faster balanced clusterings in high dimension
