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.
Inapproximability for Local Correlation Clustering and Dissimilarity Hierarchical Clustering
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
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.
citation-role summary
background 1
citation-polarity summary
fields
cs.DS 1years
2025 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Learning-Augmented Hierarchical Clustering
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.