Abstract-Vi anser k-median klustring i finita metriska utrymmen och k-medel klustring i euklideiska utrymmen, i inställningen där k är en del av inmatningen (inte en konstant). För k-means problemet, Ostrovsky et al. [18] visar att om det optimala (k −1)-medelvärdet för klustringen av indatan är dyrare än det optimala k-medelvärdet som klustrar med en faktor på 1/ på 2, då kan man uppnå en (1 + f ( på))-uppskattning till k-medelvärdena optimalt i tid polynom i n och k genom att använda en variant av Lloyds algoritm. I detta arbete förbättrar vi avsevärt denna tillnärmningsgaranti. Vi visar att endast med tanke på villkoret att (k-1)-medelvärdet optimalt är dyrare än k-medelvärdet optimalt med en faktor 1+α för vissa konstanta α > 0, kan vi få en PTAS. I synnerhet, enligt detta antagande, för alla  på > 0 vi uppnå en (1 +  på)-uppskattning till k-medelvärden optimal i tiden polynom i n och k, och exponentiellt i 1/ på och 1/α. På så sätt frikopplar vi hållfastheten i antagandet från approximationsförhållandets kvalitet. Vi ger också en PTAS för k-median problemet i ändliga mått enligt det analoga antagandet också. För k-medelvärden ger vi dessutom en randomiserad algoritm med förbättrad drifttid för n O(1) (k log n) poly(1/ och1/α). Vår teknik får också en PTAS under antagandet av Balcan et al. [4] att alla (1 + α) approximationer ligger nära ett önskat målkluster, om alla målkluster har större storlek än δn och α > 0 är konstanta. Observera att motivationen hos Balcan et al. [4] är att för många klusterproblem är den objektiva funktionen endast en indikation på det verkliga målet att komma nära målet. Ur detta perspektiv är vår förbättring att när det gäller k-medel i euklideiska utrymmen minskar vi avståndet från klustret till målet från O(δ) till δ när alla målkluster är stora, och för k-median förbättrar vi det "storhetstillstånd" som krävs [4] för att komma exakt δ-nära från O(δn) till δn. Våra resultat bygger på ett nytt begrepp om klusterstabilitet.
Baserat på begreppet stabilitet, Awasthi et al. REF presenterade PTAS för problemen med k-medel och k-mediankluster.
Stability Yields a PTAS for k-Median and k-Means Clustering
{'venue': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'journal': '2010 IEEE 51st Annual Symposium on Foundations of Computer Science', 'mag_field_of_study': ['Mathematics', 'Computer Science']}