# Maximizing Agreements for Ranking, Clustering and Hierarchical Clustering via MAX-CUT

arXiv: https://arxiv.org/abs/2102.11548 · HTML: https://mlsanity.com/paper/2102.11548/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2021.

## Built on by (most cited first, 4 of 4)

- [Hierarchical clustering with dot products recovers hidden tree structure](https://mlsanity.com/paper/2305.15022/) (2023)
- [Tree Learning: Optimal Algorithms and Sample Complexity](https://mlsanity.com/paper/2302.04492/) (2023)
- [The Complexity of Finding Local Optima in Contrastive Learning](https://mlsanity.com/paper/2509.16898/) (2025)
- [A Revenue Function for Comparison-Based Hierarchical Clustering](https://mlsanity.com/paper/2211.16459/) (2022)

## Abstract (arXiv)

In this paper, we study a number of well-known combinatorial optimization problems that fit in the following paradigm: the input is a collection of (potentially inconsistent) local relationships between the elements of a ground set (e.g., pairwise comparisons, similar/dissimilar pairs, or ancestry structure of triples of points), and the goal is to aggregate this information into a global structure (e.g., a ranking, a clustering, or a hierarchical clustering) in a way that maximizes agreement with the input. Well-studied problems such as rank aggregation, correlation clustering, and hierarchical clustering with triplet constraints fall in this class of problems. We study these problems on stochastic instances with a hidden embedded ground truth solution. Our main algorithmic contribution is a unified technique that uses the maximum cut problem in graphs to approximately solve these problems. Using this technique, we can often get approximation guarantees in the stochastic setting that are better than the known worst case inapproximability bounds for the corresponding problem. On the negative side, we improve the worst case inapproximability bound on several hierarchical clustering formulations through a reduction to related ranking problems.