Vi överväger klusterproblem med icke-uniforma nedre gränser och yttre gränser, och få de första approximativa garantierna för dessa problem. Vi har en uppsättning F av faciliteter med lägre gränser {L i } i och en uppsättning D av kunder som ligger i ett gemensamt metriska utrymme {c(i, j)} i,j till F  till D, och gränser k, m. En genomförbar lösning är ett par S  på F, σ : D → S  och {out}, där σ specificerar klientuppdragen, så att  och ≤ k, I den nedre gränsen min-sum-of-radii med utliers (LBkSRO) problem, är målet att minimera i.S max j till σ −1 (i) c(i, j), och i den nedre avgränsade k-supplier med utliers (LBkSupO) problem, målet är att minimera max i.S max j till −1 (i) c(i, j). Vi får en approximationsfaktor på 12,365 för LBkSRO, som förbättras till 3,83 för nonoutlier-versionen (dvs. m = 0). Dessa utgör också de första approximationsgränserna för målet min-sum-ofradii när vi betraktar lägre gränser och yttre gränser separat. Vi tillämpar den ursprungliga-dual metoden för avslappning där vi Lagrangify  till ≤ k restriktion. Det viktigaste tekniska bidraget och nyheten med vår algoritm är att vi avgår från det standardparadigm som används för sådana begränsade problem, vi får en O(1)-uppskattning trots att vi inte får en Lagrangian-multiplikatorbevarande algoritm för Lagrangian avkoppling. Vi anser att våra idéer har en bredare tillämplighet på andra klusterproblem med outliers också. Vi får approximativa faktorer på 5 respektive 3 för LBkSupO och dess icke-outlier version. Dessa är de första approximativa resultaten för k-leverantör med icke-uniforma nedre gränser.
Ahmadian och Swamy REF anser att kombinationen av k-supplier med utliers med (icke-uniforma) nedre gränser och härleda en 5- approximation.
Approximation Algorithms for Clustering Problems with Lower Bounds and Outliers
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}