Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LP HIERARCHIES:
Reports tagged with LP hierarchies:
TR16-117 | 31st July 2016
Mrinalkanti Ghosh, Madhur Tulsiani

#### From Weak to Strong LP Gaps for all CSPs

Revisions: 1

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\left(\frac{\log n}{\log \log n}\right)$ levels of the Sherali-Adams hierarchy on instances ... more >>>

ISSN 1433-8092 | Imprint