Utformningen av approximationsalgoritmer för klusterpunkter i metriska utrymmen är ett blomstrande forskningsområde, med stor ansträngning att få en bättre förståelse för approximationsgarantierna för många objektiva funktioner som k-median, k-medel och min-sum kluster. Denna strävan efter bättre approximation algoritmer drivs delvis av den implicita förhoppningen att bättre approximationer också kommer att ge mer exakta kluster. Särskilt när det gäller problem som att gruppera proteiner efter funktion, eller gruppera bilder efter ämne, är det verkliga syftet att matcha någon okänd korrekt "mål" klustering och den implicita förhoppningen är att ungefär optimera dessa objektiva funktioner faktiskt kommer att producera en klustering som är nära detta mål när det gäller hur datapunkter är kluster. I detta dokument visar vi att om vi gör detta implicita antagande explicit, dvs. om vi antar att vårt fall uppfyller villkoret att varje c-tillnärmning till det givna klustermålet 0 är nära målet, då kan vi effektivt producera kluster som ligger nära målet, även för värden c för vilka en c-uppskattning är NP-hård. Vi kallar detta villkor (c,  på)-tillnärmning-stabilitet och visar att vi kan uppnå denna garanti för alla konstant c > 1, för tre viktiga och brett studerade objektiva funktioner, nämligen k-median, k-medel, och min-sum mål. Således kan vi prestera nästan lika bra i termer av avstånd till målet klustering som om vi kunde approxima målet till denna NP-hård värde. Det vill säga, under antagandet att c-uppskattningar är bra lösningar, kan vi närma oss målet även om det i allmänhet är svårt att uppnå en c-uppskattning till målet.
Tillnärmning Stabilitet Balcan et al. REF definierade (α, ) - ungefärlig stabilitet, och visade algoritmer som returnerade nära-optimala lösningar för k-median och k-medelvärden när α > 1, och min-sum när α > 2.
Approximate clustering without the approximation
{'venue': 'In SODA ’09: Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms', 'journal': None, 'mag_field_of_study': ['Computer Science']}