\documentclass[12pt]{article} \usepackage{wide,amsmath} $\newcommand{\indx}{{\it index}}$ \def\xhat{{\hat x}} \def\what{{\hat w}} \def\zhat{{\hat z}} \def\Phat{{\hat P}} \parindent0pt

Max Cut by Semidefinite Programming

Quadratic formulation

Vector relaxation:

Embeddings

Rounding:

Summary

2 hours from here to end

Graph Coloring

3-coloring

Relax:

Rounding?

Finding the independent set:

Min Ratio Cut

Lead-In: Max-Flow Min-Cut

Probably cover after introducing ratio cut.

Find $s$-$t$ mincut

Motivation

Common task: computation/simulation over a mesh.

Suppose you want to parallelize

Graph bisection

$b$-balanced separator

Divide and conquer

Ratio Cut

Definition:

Use to find separator

why good?

given above, can find 1/3-2/3 cut that is close to minimum value ILP

Relaxation:

Embeddings

Goal

How do we measure error in rounding?

Every metric (isometric) embeddable in $\ell_\infty$

Isometric Embedding in $\ell_2$ tractable

We are actually going to round via embedding in $\ell_1$:

Embedding

Algorithm

Gap is tight:

Extensions