Pith. sign in

REVIEW 1 cited by

Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2010.01459 v1 pith:CVRN6JNS submitted 2020-10-04 cs.DS cs.CC

Vaggos Chatziafratis , Neha Gupta , Euiwoong Lee This is my paper · ORCID
classification cs.DScs.CC
keywords clusteringlocalassumingcorrelationdissimilarityhardnesshierarchicalresults
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

We present hardness of approximation results for Correlation Clustering with local objectives and for Hierarchical Clustering with dissimilarity information. For the former, we study the local objective of Puleo and Milenkovic (ICML '16) that prioritizes reducing the disagreements at data points that are worst off and for the latter we study the maximization version of Dasgupta's cost function (STOC '16). Our APX hardness results imply that the two problems are hard to approximate within a constant of 4/3 ~ 1.33 (assuming P vs NP) and 9159/9189 ~ 0.9967 (assuming the Unique Games Conjecture) respectively.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Learning-Augmented Hierarchical Clustering

    cs.DS 2025-06 conditional novelty 7.0 of 10

    With a noisy oracle that says which of three points splits off first, hierarchical clustering achieves constant approximation for Dasgupta and near-optimal Moseley-Wang, bypassing known hardness.

Pith tools