An exact algorithm for stable instances of the \begin{document}$ k $\end{document} -means problem with penalties in fixed-dimensional Euclidean space

We study stable instances of the \begin{document}$ k $\end{document} -means problem with penalties in fixed-dimensional Euclidean space. An instance of the problem is called \begin{document}$ \alpha $\end{document} -stable if this instance exists a sole optimal solution and the solution keeps unchanged when distances and penalty costs are scaled by a factor of no more than \begin{document}$ \alpha $\end{document} . Stable instances of clustering problem have been used to explain why certain heuristic algorithms with poor theoretical guarantees perform quite well in practical. For any fixed \begin{document}$ \epsilon > 0 $\end{document} , we show that when using a common multi-swap local-search algorithm, a \begin{document}$ (1+\epsilon) $\end{document} -stable instance of the \begin{document}$ k $\end{document} -means problem with penalties in fixed-dimensional Euclidean space can be solved accurately in polynomial time.