Local Guarantees in Graph Cuts and Clustering

on YouTube ↗28m

" summary

Defines min-max variants of cuts and correlation clustering, gives an LP relaxation and a deterministic ball-growing rounding that picks a 1/7 ball then a 3/7 cluster to get a constant bound on complete graphs (proved R7 approximation), and a modified approach for general graphs that yields a root-n approximation by removing edges with LP length >1/√n and BFS layering to bound per-vertex errors. Presents an integrality-gap cycle example and leaves open improving the 7 and √n factors.

AI-written summary · about

" chapters (7)

1. 0:00Intro
2. 3:20Correlation clustering
3. 4:05Mistakes in clustering
4. 4:35Goal of the algorithm
5. 5:05Perfect clustering
6. 5:37Triangles
7. 9:17Global Objective