Vi undersöker komplexiteten i att lösa stabila eller perturbation-resilienta fall av k-means och kmedian klustering i fast dimension Euclidean metrics (eller mer allmänt dubblering metrics). Begreppet stabila eller nötningståliga fall infördes av Bilu och Linial [2010] och Awasthi, Blum och Sheffet [2012]. I vårt sammanhang säger vi att en k-means instans är α-stabil om det finns en unik optimal lösning som förblir oförändrad om avstånden (icke-uniformt) sträcks med en faktor som högst α. Stabila klusterfall har studerats för att förklara varför heuristik som Lloyds algoritm fungerar bra i praktiken. I detta arbete visar vi att för alla fasta  till > 0, (1 +  på)-stabila fall av k-medel i dubbleringsmått, som inkluderar fast-dimensionella Euclidean mätvärden, kan lösas i polynom tid. Mer exakt, vi visar en naturlig multi-swap lokala-sök algoritm i själva verket finner den optimala lösningen för (1 +  på)-stabila fall av k-medel och k-median i ett polynom antal iterationer. Vi kompletterar detta resultat genom att visa att under en rimlig PCP hypotes är detta i huvudsak tight: att när dimension d är en del av indata, det finns en fast  på 0 > 0 sådan det finns inte ens en PTAS för (1 +  på 0)-stabila k-medelvärden i R d om inte NP=RP. För att göra detta anser vi en robust egenskap hos CSPs; kalla en instans stabil om det finns en unik optimal lösning x * och för någon annan lösning x ′, antalet otillfredsställda klausuler är proportionell mot Hamming avstånd mellan x * och x ′. Dinur, Goldreich, och Gur har redan visat stabil QSAT är svårt att approximera för vissa konstant Q [16], vår hypotes är helt enkelt att stabil QSAT med avgränsad variabel förekomst är också svårt (det finns faktiskt arbete som pågår för att bevisa denna hypotes). Med tanke på denna hypotes, vi anser "stabilitet-bevarande" minskningar för att bevisa vår hårdhet för stabila k-medel. Sådana minskningar verkar vara mer sköra och invecklade än standard L-minskningar och kan vara till ytterligare nytta för att visa att andra stabila optimeringsproblem är svåra att lösa.
Oberoende och parallellt med detta arbete, Friggstad et al. REF visade att för varje fast d 1 och α > 1, kan α-multiplikativa perturberingsresistenta fall av diskreta k-medelvärden och k-median (där centren måste vara från själva datapunkterna) i mätvärden med dubbleringsdimension d lösas med tiden O n d O(d) (α−1) −O(d/(α−1)) k.
Exact Algorithms and Lower Bounds for Stable Instances of Euclidean k-Means
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}