  Correlation Clustering is an elegant model that captures fundamental graph
cut problems such as Min $s-t$ Cut, Multiway Cut, and Multicut, extensively
studied in combinatorial optimization. Here, we are given a graph with edges
labeled $+$ or $-$ and the goal is to produce a clustering that agrees with the
labels as much as possible: $+$ edges within clusters and $-$ edges across
clusters. The classical approach towards Correlation Clustering (and other
graph cut problems) is to optimize a global objective. We depart from this and
study local objectives: minimizing the maximum number of disagreements for
edges incident on a single node, and the analogous max min agreements
objective. This naturally gives rise to a family of basic min-max graph cut
problems. A prototypical representative is Min Max $s-t$ Cut: find an $s-t$ cut
minimizing the largest number of cut edges incident on any node. We present the
following results: $(1)$ an $O(\sqrt{n})$-approximation for the problem of
minimizing the maximum total weight of disagreement edges incident on any node
(thus providing the first known approximation for the above family of min-max
graph cut problems), $(2)$ a remarkably simple $7$-approximation for minimizing
local disagreements in complete graphs (improving upon the previous best known
approximation of $48$), and $(3)$ a $1/(2+\varepsilon)$-approximation for
maximizing the minimum total weight of agreement edges incident on any node,
hence improving upon the $1/(4+\varepsilon)$-approximation that follows from
the study of approximate pure Nash equilibria in cut and party affiliation
games.
