Local guarantees in graph cuts and clustering

DOI10.1007/978-3-319-59250-3_12MaRDI QIDQ2401152zbMATH OpenOpenAlexFDO

Authors Moses Charikar, Neha Gupta, Roy Schwartz

Publication date 31 August 2017

Full work available at URL https://arxiv.org/abs/1704.00355

zbMATH Keywords

linear programmingapproximation algorithmscorrelation clusteringgraph cuts

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Minimax problems in mathematical programming (90C47)

Abstract: 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(sqrtn)$-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.

Recommendations

• Min-max correlation clustering via multicut
• Algorithms - ESA 2003
• Correlation clustering, maximizing agreements via semidefinite programming
• Correlation clustering in general weighted graphs
• Correlation clustering

Cited in

(8)

• Fair correlation clustering with global and local guarantees
• Efficient enumeration of the optimal solutions to the correlation clustering problem
• Min-max correlation clustering via multicut
• Approximation algorithm for min-max correlation clustering problem with outliers
• Approximation Algorithms for the Capacitated Min–Max Correlation Clustering Problem
• _p-norm multiway cut
• Fixed parameter approximation scheme for min-max \(k\)-cut
• Fixed parameter approximation scheme for min-max \(k\)-cut

This page was built for publication: Local guarantees in graph cuts and clustering

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401152)