Sparsifizierung von Korrelationsclustering: Neue Approximationsergebnisse

In einer wegweisenden Studie wird untersucht, wie viel Kantengewicht in der Korrelationsclustering‑Aufgabe benötigt wird, um die besten lineare Programm‑Approximationen zu erhalten. Dabei wird ein klarer Unterschied zwischen pseudometrischen und allgemein gewichteten Instanzen aufgezeigt.

Für pseudometrische Fälle liefert die Arbeit mehrere Durchbrüche: Die VC‑Dimension der Diskrepanzklasse beträgt exakt n – 1, was additive ε‑Coresets der optimalen Größe ~O(n/ε²) ermöglicht. Außerdem zeigen die Autoren, dass an jedem LP‑Scheitelpunkt höchstens n choose 2 Dreiecksungleichungen aktiv sind, was einen exakten Cutting‑Plane‑Solver erlaubt. Ein sparsifiziertes LP‑PIVOT‑Verfahren, das fehlende LP‑Marginale über Dreiecksungleichungen interpoliert, erreicht eine robuste 10/3‑Approximation – abgesehen von einem additiven Term, der durch eine empirisch berechenbare Qualitätsstatistik kontrolliert wird – sobald etwa ~n³⁄² Kanten beobachtet werden. Diese Schwelle wird als optimal bewiesen.

Im Gegensatz dazu zeigen die Autoren, dass ohne pseudometrische Struktur jede Methode, die nur o(n) zufällig ausgewählte Kanten nutzt, ein unbegrenztes Approximationsergebnis liefert. Damit wird klar, dass die pseudometrische Bedingung nicht nur die Lösbarkeit, sondern auch die Robustheit des Korrelationsclustering gegenüber unvollständigen Daten bestimmt.