I detta dokument introducerar och studerar vi problemet med icke-enformig k-Center (NUkC). Med tanke på en ändlig metriska utrymme (X, d) och en samling av bollar av radi {r 1 ≥ · · · ≥ r k }, NUkC problemet är att hitta en placering av sina centra på det metriska utrymmet och hitta den minsta dilatation α, så att föreningen av bollar med radien α · r i runt ith centrum täcker alla punkter i X. Detta problem uppstår naturligtvis som ett min-max fordon routing problem med flottor av olika hastigheter. NUKC-problemet generaliserar det klassiska k-centerproblemet när alla k-radier är samma (som kan antas vara 1 efter skalning). Det generaliserar också k-center med ytterkanter (kCwO för kort) problem när det finns k bollar med radie 1 och bollar med radie 0. Det finns 2- approximation och 3- approximation algoritmer kända för dessa problem respektive; den förra är bäst möjligt om inte P=NP och den senare förblir oförbättrad i 15 år. Vi observerar först att ingen O(1)-uppskattning är möjlig till optimal utvidgning om inte P=NP, vilket innebär att NUkC-problemet är mer icke-trivial än de två ovan nämnda problemen. Vårt huvudalgoritmiska resultat är ett (O(1), O(1))-bi-kriteria approximation resultat: vi ger en O(1)- approximation till den optimala dilatationen, men vi kan öppna  och (1) centra för varje radi. Våra tekniker gör det också möjligt för oss att bevisa en enkel (uni-criteria), optimal 2- approximation till kCwO problem förbättra på den långvariga 3-faktorn. Vårt huvudsakliga tekniska bidrag är ett samband mellan NUkC-problemet och de så kallade brandmännens problem på träd som nyligen har studerats i TCS-gemenskapen. Vi visar att NUkC är lika svårt som brandmännens problem. Även om vi inte vet om det motsatta är sant, kan vi anpassa idéer från nya verk [3, 1] på icke-triviala sätt för att få vår konstanta faktor bi-criteria approximation.
Den approximationsfaktor för k-center problem med utliers förbättrades till 2 i REF.
The Non-Uniform k-Center Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}