Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
Questo lavoro migliora i tempi di esecuzione degli algoritmi di approssimazione per i problemi di clustering -median e -means in spazi euclidei a bassa dimensione e dimostra che tale miglioramento è quasi ottimale, fornendo un limite inferiore corrispondente basato sull'ipotesi Gap Exponential Time.