K-center problemet är en klassisk anläggning plats problem, där ges en kant-viktad graf G = (V, E) en är att hitta en delmängd av k hörn S, så att varje vertex i V är "nära" till vissa vertex i S. Den approximation status för detta grundläggande problem är väl förstådd, som en enkel 2- approximation algoritm är känd för att vara tight. Följaktligen studerades olika förlängningar. I den kapacierade versionen av problemet tilldelas varje vertex en kapacitet, som är en strikt övre gräns för antalet kunder en anläggning kan tjäna, när den ligger på denna vertex. En konstant faktor approximation för kapaciated k-center erhölls förra året av Cygan, Hajiaghayi och Khuller [FOCS'12], som nyligen förbättrades till en 9- approximation av An, Bhaskara och Svensson [arXiv'13]. I en annan generalisering av problemet vissa kunder (benämns som avvikande) kan förbises. Här får vi dessutom ett heltal p och målet är att tjäna exakt p-klienter, som algoritmen är fri att välja. 2001 Charikar m.fl. [SODA'01] presenterade en tre approximation för k-center problem med avvikande. I denna uppsats överväger vi en gemensam generalisering av de två förlängningar som tidigare studerats separat, d.v.s. Vi jobbar med det kapacierade k-centret med utlirar. Vi presenterar den första konstant faktor approximation algoritm med approximation förhållande 25 även för fall av icke-uniform hård kapacitet.
Cygan och Kociumaka REF ger en 25- approximation för kapaciated k-center problem med utliers.
Constant Factor Approximation for Capacitated k-Center with Outliers
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}