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
-
Cluster Deletion is as Hard to Approximate as Vertex Cover
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.
-
Constrained Correlation Clustering: Towards Optimality
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.
-
1.64-Approximation for Chromatic Correlation Clustering via Chromatic Cluster LP
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 Faster Algorithm for Constrained Correlation Clustering
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.
-
Hardness and Approximation for Coloring Digraphs
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.
-
CKR Partitions and Lower Bounds for Constrained Correlation Clustering and Variants
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.