Cluster Deletion is NP-hard to approximate within sqrt(2)-epsilon, and UGC-hard within 2-epsilon, matching the known 2-approximation and answering an open question about Cluster Editing versus Bad Triangle Transversal.
Journal of Computer and System Sciences , volume =
7 Pith papers cite this work, alongside 308 external citations. Polarity classification is still indexing.
7
Pith papers citing it
308
external citations · Crossref
representative citing papers
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.
Constrained Correlation Clustering is shown to be approximable within a factor just under 16/7, while a UGC-based lower bound of 2 proves the Cluster Deletion 2-approximation is optimal.
A new (18/11 + ε)-approximation algorithm for Chromatic Correlation Clustering is obtained by introducing a chromatic cluster linear program and combining cluster-based with pivot-based rounding.
A deterministic Õ(n^3)-time 16-approximation for constrained correlation clustering, plus a derandomized pivot algorithm, a tight lower bound, and a new node-weighted variant.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
Under UGC, cluster deletion, constrained correlation clustering, and minimum weakness strong triadic closure are hard to approximate within 2-epsilon, while a CKR decomposition of the standard LP gives an expected 3-approximation for constrained correlation clustering.
citing papers explorer
-
Query Lower Bounds for Correlation Clustering under Memory Constraints
The work proves that approximating correlation clustering to additive εn² error requires Ω(n/ε²) adjacency-matrix queries, with stronger bounds under memory constraints in random and general query models.