Approximate Clustering with Same-Cluster Queries
From MaRDI portal
Publication:4993306
DOI10.4230/LIPIcs.ITCS.2018.40zbMath1462.68153arXiv1704.01862OpenAlexW2613497313MaRDI QIDQ4993306
Anup Bhattacharya, Nir Ailon, Amit Kumar, Ragesh Jaiswal
Publication date: 15 June 2021
Full work available at URL: https://arxiv.org/abs/1704.01862
Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items (2)
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tight lower bound instances for \(k\)-means++ in two dimensions
- A bad instance for \texttt{k-means++}
- 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
- Improved and simplified inapproximability for \(k\)-means
- A local search approximation algorithm for \(k\)-means clustering
- Center-based clustering under perturbation stability
- Which problems have strongly exponential complexity?
- Clustering with Interactive Feedback
- Linear-time approximation schemes for clustering problems in any dimensions
- A PTAS for k-means clustering based on weak coresets
- Adaptive Sampling for k-Means Clustering
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- k-means requires exponentially many iterations even in the plane
- The effectiveness of lloyd-type methods for the k-means problem
- Clustering under approximation stability
- The PCP theorem by gap amplification
- On the complexity of \(k\)-SAT
This page was built for publication: Approximate Clustering with Same-Cluster Queries
