Det mest kända och allmänt förekommande klusterproblem som påträffas i nästan varje vetenskapsgren är utan tvekan k-MEANS: med tanke på en uppsättning datapunkter och en parameter k, välj k-centra och dela datapunkterna i k-kluster runt dessa centrum så att summan av kvadrater av avstånden mellan punkterna till deras klustercenter minimeras. Vanligtvis ligger dessa datapunkter i Euclidean space R d för några d ≥ 2. k-MEANS och de första algoritmerna för det infördes på 1950-talet. Under de senaste sex decennierna har hundratals tidningar studerat detta problem och olika algoritmer har föreslagits för det. Den mest använda algoritmen i praktiken kallas Lloyd-Forgy, som också kallas "the" k-MEANS algoritm, och olika förlängningar av den fungerar ofta mycket bra i praktiken. De kan dock producera lösningar vars kostnad är godtyckligt stor jämfört med den optimala lösningen. Kanungo m.fl. [2004] analyserade en mycket enkel lokal sökning heuristic för att få en polynom-tid algoritm med approximation förhållande 9+ för alla fasta > 0 för k-MEANS i Euclidean utrymme. Att hitta en algoritm med en bättre värsta möjliga approximation garanti har förblivit en av de största öppna frågorna inom detta område, särskilt om man kan få en sann PTAS för fast dimension Euclidean utrymme. Vi löser detta problem genom att visa att en enkel lokal sökalgoritm ger en PTAS för k-MEANS för R d för varje fast d. Mer exakt, för varje felparameter > 0, den lokala sökalgoritmen som anser att swappar på upp till ρ = d O(d) · − O(d/ ) center åt gången kommer att producera en lösning med exakt k-centra vars kostnad är som mest en (1+ )-faktor större än den optimala lösningen. Vår analys sträcker sig mycket lätt till de mer allmänna inställningar där vi vill minimera summan av q'th befogenheter av avstånden mellan datapunkter och deras klustercenter (i stället för summan av kvadrater av avstånd som i k-MEANS) för varje fast q ≥ 1 och där metriska kan inte vara Euclidean men fortfarande har fast dubblering dimension.
I självständigt arbete, Friggstad et al. REF visade att lokal sökning är en polynom-tids approximationssystem för k-medel i fallet med en d-dimensionell Euclidean utrymme för en lokal sökning parameter inställning av s " d Opdq ́Opd{ q.
Local Search Yields a PTAS for k-Means in Doubling Metrics
{'venue': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'journal': '2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}