We　study　stable　instances　of　the　k-means　problem　with　penalties　in　fixed-dimensional　Euclidean　space.　An　instance　of　the　problem　is　called　alpha-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　alpha.　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　epsilon　＞　0,　we　show　that　when　using　a　common　multi-swap　local-search　algorithm,　a　(1　+　epsilon)-stable　instance　of　the　k-means　problem　with　penalties　in　fixed-dimensional　Euclidean　space　can　be　solved　accurately　in　polynomial　time.