Abstract-Clustering är ett klassiskt ämne i optimering med k-means är ett av de mest grundläggande sådana problem. I avsaknad av några restriktioner på indata, den mest kända algoritmen för k-medel med en bevisbar garanti är en enkel lokal sök heuristiska ger en approximation garanti på 9 +, ett förhållande som är känt för att vara snäv med avseende på sådana metoder. Vi övervinner denna barriär genom att presentera en ny primal-dual strategi som gör det möjligt för oss att (1) utnyttja den geometriska strukturen av k-medel och (2) för att tillfredsställa den hårda begränsning som i de flesta k-kluster väljs utan att försämra approximationsgarantin. Vårt huvudresultat är en 6.357-approximationsalgoritm med avseende på den vanliga LP-avslappningen. Våra tekniker är ganska allmänna och vi visar också förbättrade garantier för den allmänna versionen av k-medelvärden där det underliggande metriska inte krävs för att vara Euclidean och för k-median i Euclidean metrics.
För k-medel är den bästa approximationen känd 6.357 REF.
Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms
{'venue': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}