Fair Colorful k-Center Clustering

Ein Beispiel für ein buntes k-Zentrum besteht aus Punkten in einem metrischen Raum, die rot oder blau gefärbt sind, zusammen mit einem ganzzahligen k und einer Abdeckungsanforderung für jede Farbe. Ziel ist es, den kleinsten Radius so zu finden, dass es Radiusbälle um k der Punkte gibt, die die Abdeckungsanforderungen erfüllen.Die Motivation hinter diesem Problem ist zweierlei: Erstens aus Fairness-Überlegungen: Jede Farbe / Gruppe sollte eine ähnliche Leistungsgarantie erhalten, und zweitens aus den algorithmischen Herausforderungen, die es stellt: Dieses Problem kombiniert die Schwierigkeiten der Clusterbildung mit dem Teilsummenproblem. Insbesondere zeigen wir, dass diese Kombination zu einer starken Integritätslücke führt, die die Grenzen für mehrere natürliche lineare Programmierrelaxationen unterschreitet. Unser Hauptergebnis ist ein effizienter Approximationsalgorithmus, der diese Schwierigkeiten überwindet, um eine Annäherungsgarantie von 3 zu erreichen, die fast der engen Approximationsgarantie von 2 für das klassische k-Zentrum-Problem entspricht, das dieses Problem verallgemeinert.