Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LP HIERARCHIES:
Reports tagged with LP hierarchies:
TR16-117 | 31st July 2016
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 >>>