  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.
