Talks - Fall 2017

Linear optimization in a 2-dimensional polytope

Title

Speaker

Date

Time

Venue

Abstract

From Weak to Strong LP Gaps for All CSPs

Mrinalkanti Ghosh

24 Aug, 2017

3 pm

KD102

We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations.

We show that for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by $\Omega(\log n/\log \log n$ levels of the Sherali-Adams hierarchy on instances of size $n$.

It was proved by Chan et al. [FOCS 2013] (and recently strengthened by Kothari et al. [STOC 2017]) that for CSPs, any polynomial size LP extended formulation is no stronger than relaxations obtained by a super-constant levels of the Sherali-Adams hierarchy.

Combining this with our result also implies that any polynomial size LP extended formulation is no stronger than simply the ``basic'' LP, which can be thought of as the base level of the Sherali-Adams hierarchy. This essentially gives a dichotomy result for approximation of CSPs by polynomial size LP extended formulations.

Based on joint work with Madhur Tulsiani

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator