Problemet Euclidean k-means är ett klassiskt problem som har studerats i stor utsträckning inom den teoretiska datavetenskapen, maskininlärningen och den beräkningsgeometrin. I detta problem, vi ges en uppsättning n punkter i Euclidean utrymme R d, och målet är att välja k centrum punkter i R d så att summan av kvadraten avstånd av varje punkt till dess närmaste centrum minimeras. De bästa approximationsalgoritmer för detta problem inkluderar en polynom tid konstant faktor approximation för allmän k och en (1 +  på)- approximation som körs i tiden poly(n) exp(k/ på). I den andra ytterligheten är NP-hårdhet det enda kända beräkningskomplexa resultatet för detta problem [1]. Den största svårigheten att få hårdhet resultat härrör från den euklideiska naturen av problemet, och det faktum att någon punkt i R d kan vara en potentiell centrum. Denna lucka i förståelse lämnade öppen den spännande möjligheten att problemet kan erkänna en PTAS för alla k, d. I detta papper ger vi den första hårdheten av approximation för Euclidean k-means problem. Konkret visar vi att det finns en konstant  på > 0 så att det är NP-hård att approximera kmeans mål att inom en faktor på (1+ på). Vi visar detta genom en effektiv minskning från vertex cover problem på triangelfria grafer: med tanke på en triangelfri graf, är målet att välja det minsta antalet hörn som inträffar på alla kanter. Dessutom ger vi ett bevis på att de nuvarande bästa hårdhetsresultaten för vertex täcker kan överföras till triangelfria grafer. För att visa detta omvandlar vi G, en känd hård vertex cover instans, genom att ta en graf produkt med en lämpligt vald graf H, och visar att storleken på (normaliserad) maximal oberoende uppsättning nästan exakt bevaras i produktgrafen med hjälp av en spektral analys, som kan vara av oberoende intresse.
Även hitta en (1 + ) approximation med varierande (k, d) är svårt REF.
The Hardness of Approximation of Euclidean k-means
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}