Almost Optimal Lower Bounds under Almost ETH for Approximating Euclidean k-means

arXiv:2611.14892 · cs.CG, cs.CC, cs.DS, stat.ML · Submitted 2026-11-11 · Read on arXiv

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

Related papers