I detta dokument presenterar vi en ny iterativ avrundningsram för många klusterproblem. Med hjälp av detta får vi en (α 1 + ε ≤ 7.081 + ε) - approximationsalgoritm för k-median med utliers, avsevärt förbättra på den stora implicita konstant approximation förhållande Chen. För k-medel med avvikelser ger vi en (α 2 + ε ≤ 53.002+ε)-uppskattning, vilket är den första O(1)-uppskattningen för detta problem. Det iterativa algoritmramverket är mycket mångsidigt; vi visar hur det kan användas för att ge α 1 - och (α 1 + ε) - approximation algoritmer för matroid och knapsack median problem respektive, förbättra på de tidigare bästa approximations förhållande av 8 på grund av Swamy och 17.46 på grund av Byrka et al. Den naturliga LP-avslappning för k-median / k-medel med avvikande problem har en obegränsad integrality gap. Trots detta negativa resultat visar vårt iterativa avrundningsramverk att vi kan runda en LP-lösning till en nästan integrerad lösning av små kostnader, där vi har högst två fraktionerat öppna anläggningar. Således uppstår integralitetsgapet för LP på grund av gapet mellan nästan integrala och fullt integrerade lösningar. Sedan, med hjälp av ett förbehandlingsförfarande, visar vi hur man konverterar en nästan integrerad lösning till en fullt integrerad lösning som bara förlorar en konstant faktor i approximationsförhållandet. Genom vidare användning av en sparifieringsteknik kan den additiva faktorförlusten till följd av omvandlingen minskas till vilken ε > 0 som helst. • Teori för beräkning → Anläggningens läge och klusterbildning;
Mycket nyligen, Krishnaswamy et al. I Ref föreslogs en generisk ram för kluster med avvikande delar.
Constant approximation for k-median and k-means with outliers via iterative rounding
{'venue': 'STOC 2018', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}