Two-Point Local Optimality in $k$-Means via Boundary-Point Screening

Wenlong Lyu, Xujie Xiao, Yuheng Jia

Lloyd's algorithm and the discrete local (D-local) optimization method (Li et al., 2025) for $k$-means provide only weak local-optimality guarantees, and their solution quality rem…