Local Guarantees in Graph Cuts and Clustering

Moses Charikar, Neha Gupta, Roy Schwartz

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 opti…