K-center problemet är en klassisk kombinatorial optimering problem som ber att hitta k-centra sådan att det maximala avståndet för någon ingångspunkt i en uppsättning P till dess tilldelade centrum minimeras. Problemet möjliggör eleganta 2- approximationer. Situationen blir dock betydligt svårare när man lägger till begränsningar i problemet. Vi ställer frågan om allmänna metoder kan härledas för att omvandla en approximationsalgoritm för ett klusterproblem med vissa begränsningar till en approximationsalgoritm som respekterar en begränsning mer. Vår begränsning av valet är integritet: Här är vi ombedda att bara öppna ett center när åtminstone kunder kommer att tilldelas det. Vi visar hur man kombinerar integritet med flera andra begränsningar.  ACM Subject Classification F.2.2 Icke-numeriska algoritmer och problem Nyckelord och fraser Kluster är en grundläggande oövervakad inlärningsuppgift: Med tanke på en uppsättning objekt, dela upp dem i kluster, så att objekt i samma kluster är väl matchade, medan olika kluster har något som tydligt skiljer dem åt. De tre klassiska klustermålen som studeras i kombinatorisk optimering är k-center, k-median och anläggningsplats. Eftersom en punkt som P, k-center och k-median be om en uppsättning k-centra och en tilldelning av de punkter i P till de utvalda centra som minimerar ett mål. För k-center är målet det maximala avståndet för varje punkt till dess tilldelade centrum. För k-median, är det summan av avstånden för alla punkter till deras tilldelade centrum (detta kallas anslutningskostnad). Anläggningens läge begränsar inte antalet centra. Istället har varje centrum (här kallad anläggning) en öppningskostnad. Målet är att hitta en uppsättning centra så att anslutningskostnaden plus öppningskostnaden för alla valda anläggningar minimeras. I de okonstruerade versionerna kommer varje punkt att tilldelas sitt närmaste centrum. Med tillägg av begränsningar är ett annat uppdrag ofta nödvändigt för att uppfylla kraven. Mycket forskning har ägnats åt att utveckla approximationsalgoritmer för dessa tre. Den tidigaste framgångssagan är k-center: Gonzalez [20] samt Hochbaum och Shmoys [23] gav en 2-approximationsalgoritm för problemet, medan Hsu och Nemhauser [24] visade att hitta en bättre approximation är NP-hard. Sedan dess har stora ansträngningar gjorts för att närma de två andra målen till varandra. Vanligtvis kommer anläggningen plats att vara först, och överföring av nya tekniker till k-median innebär ytterligare utmaningar. Betydande tekniker som utvecklats under många decennier är LP avrundning tekniker [10, 33], giriga och primal dubbla metoder [25, 26], lokala sökalgoritmer [5, 29], och, mer nyligen, användningen av pseudo-uppskattning [32]. Det för närvarande bästa approximationsförhållandet för anläggningens läge är 1. 488 [31], medan den bästa nedre gränsen är 1.463 [21]. För k-median, den för närvarande bästa approximationsalgoritmen uppnår ett förhållande på 2.675+ [8], medan den bästa nedre gränsen är 1 + 2 e  och 1.736 [25].
Därefter tillhandahåller REF en approximationsalgoritm för ett sådant rättvist k-centerproblem med flera grupper.
Privacy preserving clustering with constraints
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}