Die Kraft des einheitlichen Samplings für Coresets

Motiviert durch praktische Generalisierungen der klassischen k-median und k-means Ziele, wie beispielsweise Clustering mit Größenbeschränkungen, faires Clustering und Wasserstein-Baryzentrum, führen wir ein Meta-Theorem zur Gestaltung von Coresets für Probleme des beschränkten Clustering ein. Das Meta-Theorem reduziert die Aufgabe der Coreset-Konstruktion auf eine mit einer begrenzten Anzahl von Ringinstanzen mit einem stark relaxierten additiven Fehler. Diese Reduktion ermöglicht es uns, Coresets mithilfe von einheitlichem Sampling zu konstruieren, im Gegensatz zum weit verbreiteten Wichtigkeits-Sampling, und folglich können wir die eingeschränkten Ziele leicht handhaben. Bemerkenswerterweise, und vielleicht überraschend, kann dieses einfachere Sampling-Schema Coresets liefern, deren Größe unabhängig von n ist, der Anzahl der Eingabepunkte. Unsere Technik führt zu kleineren Coresets, und manchmal zu den ersten Coresets, für eine große Anzahl von Problemen des eingeschränkten Clusters, einschließlich kapazitätsbegrenzt Clustering, fairem Clustering, euklidischem Wasserstein-Baryzentrum, Clustering in grafischen Minor-Exclusion und Polygon-Clustering unter Fréchet- und Hausdorff-Distanz. Schließlich liefert unsere Technik auch kleinere Coresets für 1-median in nieder-dimensionalen euklidischen Räumen, spezifisch der Größe O (^-15) in R^2 und O (^-16) in R^3.