Talks
Fall 2017
Low Diameter Graph Decompositions and Approximating Unique Games
Thursday, September 14th, 2017, 11:30 am–12:00 pm
Speaker:
This talk consists of two different but related results. First, we show how to approximate unique games in minor-closed graph families using linear programming and standard low diameter graph decomposition. We will illustrate the proof through the min-uncut problem. Motivated by this result, we consider graph decompositions using effective resistance as the distance measure, and show that every graph (not just minor-free graphs) has a low effective-resistance diameter graph decomposition.
Attachment | Size |
---|---|
Low Diameter Graph Decompositions and Approximating Unique Games | 140.29 KB |