COMPUTER SCIENCE/DISCRETE MATH I | |

Topic: | Integrality Gaps for Sherali-Adams Relaxations |

Speaker: | Yury Makarychev |

Affiliation: | Microsoft Research |

Date: | Monday, February 18 |

Time/Room: | 11:15am - 12:15pm/S-101 |

We prove strong lower bounds for Sherali-Adams relaxations of the MAX CUT, Vertex Cover and Sparsest Cut problems. Specifically, we show that the integrality gap of MAX CUT and Vertex Cover relaxations is 2-$\epsilon$ after n^delta rounds (where delta depends on epsilon); the integrality gap of Sparsest Cut is at least $C \max(\sqrt{\log n / (\log r + \log \log n)}$, $\log n / (r + \log \log n))$. Joint work with Moses Charikar and Konstantin Makarychev.