Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means
cs.CG, cs.CC, cs.DS, stat.ML
Submitted: 2026-11-11
Updated: 2026-11-11
Code: https://github.com/cskarthikcs/kmeans-kmedian-supplementary
Terminology
Sources
- Clustering under Constraints: Efficient Parameterized Approximation Schemes
- Almost-Polynomial Ratio Almost-ETH-Hardness of Approximating Densest k-Subgraph
Related papers
- The Rhythm of the Tiles: Narrow and Low Temperature Computation and Simulation in Synchronous Tile Self-Assembly
- k-Planar and Fan-Crossing Drawings and Transductions of Embeddable Graphs
- Covering Points with Rectangular Boundaries
- Tiling 3D Space by (Translates of) a Single Polycube is Undecidable
- Quadratic Complexity of Voronoi Diagrams in R cubed for Lines in a Single Ruling of a Regulus
- Minimum central circles: chain order, seam obstructions, and exact finite certification