Improved PTAS for the constrained \(k\)-means problem
From MaRDI portal
Publication:2424715
DOI10.1007/s10878-018-0340-4zbMath1425.90091OpenAlexW2888561234MaRDI QIDQ2424715
Neng Huang, Qilong Feng, Jianxin Wang, Jiaxin Hu
Publication date: 25 June 2019
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-018-0340-4
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
On coresets for fair clustering in metric and Euclidean spaces and their applications, A unified framework of FPT approximation algorithms for clustering problems, Improved approximation algorithms for two-stage flowshops scheduling problem, New kernels for several problems on planar graphs
Cites Work
- 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
- Partition on trees with supply and demand: kernelization and algorithms
- Improved kernel results for some FPT problems based on simple observations
- A local search approximation algorithm for \(k\)-means clustering
- NP-hardness of Euclidean sum-of-squares clustering
- Fault tolerant \(K\)-center problems
- Faster algorithms for the constrained \(k\)-means problem
- An improved FPT algorithm for almost forest deletion problem
- Parameterized computational complexity of Dodgson and Young elections
- Dealing with several parameterized problems by random methods
- Parameterized algorithms for edge biclique and related problems
- Achieving anonymity via clustering
- Solving the Chromatic Cone Clustering Problem via Minimum Spanning Sphere
- Net and Prune
- Geometric clustering
- Fixed Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs
- Linear-time approximation schemes for clustering problems in any dimensions
- Approximate clustering via core-sets
- Approximation schemes for clustering problems
- Clustering with Diversity
- A PTAS for k-means clustering based on weak coresets
- The Capacitated K-Center Problem
- Faster Algorithms for the Constrained k-Means Problem
- 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
- Least squares quantization in PCM
- A Constant Factor Approximation Algorithm for Fault-Tolerant k -Median
- Better Guarantees for $k$-Means and Euclidean $k$-Median by Primal-Dual Algorithms
- Probability Inequalities for Sums of Bounded Random Variables
- A Unified Framework for Clustering Constrained Data without Locality Property
- The effectiveness of lloyd-type methods for the k-means problem
- Parameterized Algorithms
- Turning Big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering
