English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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 at least as strong as the approximation obtained using relaxations given by c · logn/ log logn levels of the Sherali–Adams hierarchy (for some constant c > 0) 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 at most as strong as the relaxation obtained by a constant number of levels of the Sherali–Adams hierarchy (where the number of levels depend on the exponent of the polynomial in the size bound). Combining this with our result also implies that any polynomial-size LP extended formulation is at most as strong as the basic LP, which can be thought of as the base level of A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference (CCC’17) [14]. ∗NSF award number CCF-1254044. †NSF award number CCF-1254044. ACM Classification: F.2.2, G.1.6 AMS Classification: 68Q17, 90C05

From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems.