Korrelationsclustering mit Sherali-Adams

Gegeben sei ein vollständiger Graph G = (V, E), in dem jede Kante mit + oder − beschriftet ist. Das Problem des KORRELATIONSCLUSTERINGS verlangt, V in Cluster zu partitionieren, um die Anzahl der +Kanten zwischen verschiedenen Clustern und die Anzahl der −Kanten innerhalb desselben Clusters zu minimieren. KORRELATIONSCLUSTERING wurde verwendet, um eine Vielzahl von Clustering-Problemen in der Praxis zu modellieren und gehört somit zu den am häufigsten untersuchten Clustering-Formulierungen. Die Approximierbarkeit von KORRELATIONSCLUSTERINGS wurde aktiv untersucht BBC04, CGW05, ACN08 und gipfelt in einem 2.06-Approximation-Algorithmus CMSY15, der auf der Abrundung der Standard-LP-Entspannung basiert. Da die Integritätslücke für diese Formulierung 2 beträgt, bleibt die Frage offen, ob der Approximationsfaktor von 2 erreicht oder sogar überschritten werden kann. In diesem Papier beantworten wir diese Frage bejaht, indem wir zeigen, dass es einen (1.994+)-Approximation-Algorithmus gibt, der auf O(1/^2) Runden der Sherali-Adams-Hierarchie basiert. Um eine Lösung zur Sherali-Adams-Entspannung zu runden, passen wir das korrelierte Rounding an, das ursprünglich für CSPs BRSII, GSII, RT12 entwickelt wurde. Mit diesem Werkzeug erreichen wir ein Annäherungsverhältnis von 2+ für KORRELATIONSCLUSTERING. Um dieses Verhältnis zu brechen, gehen wir über die traditionelle trianguläre Analyse hinaus, indem wir ein globales Verrechnungsschema verwenden, das die Gesamtkosten der Rundung über verschiedene Dreiecke amortisiert.