Vi anser att problemet med att tillnärma en uppsättning P av n punkter i R d genom en samling av j-dimensionella lägenheter, och förlängningar därav, under standard median / medelvärde / center åtgärder, där vi vill minimera, respektive summan av avstånden från varje punkt av P till dess närmaste platta, summan av kvadraterna av dessa avstånd, eller den maximala sådana avstånd. Sådana problem kan inte approximas om inte P=NP men tillåter bi-kriterie approximationer där man tillåter en viss spelrum i både antalet lägenheter och kvaliteten på den objektiva funktionen. Vi ger en mycket enkel bi-criteria approximationsalgoritm, som producerar som mest α(k, j, n) = log n · (jk log log n) O(j) flats, som överstiger det optimala objektiva värdet för alla k j-dimensionella plattar med en faktor på högst β(j) = 2 O(j). Med tanke på denna approximation av två kriterier kan vi använda den för att godtyckligt minska approximationen, till priset av att öka antalet lägenheter. Vår algoritm har många fördelar jämfört med tidigare arbete, genom att det är mycket mer allmänt tillämplig (bredare uppsättning objektiva funktioner och klasser av kluster) och mycket effektivare -minskande den körtid som är bunden från O(n poly(k,j)) till dn · (jk) O(j). Vår algoritm är randomiserad och framgångsrik med sannolikhet 1/2 (lätt förstärkt till sannolikheter godtyckligt nära 1).
Dessutom erbjuder REF en bi-kriteria lösning för ett annat relaterat problem med att tillnärma en uppsättning punkter genom en samling lägenheter; de använder konvexa avkopplingar för att lösa sina problem och är begränsade till bi-kriteria lösningar, till skillnad från våra.
Bi-criteria linear-time approximations for generalized k-mean/median/center
{'venue': "SCG '07", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}