文章基本信息

标题：From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
本地全文：下载
作者：Mrinalkanti Ghosh ; Madhur Tulsiani
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2018
卷号：14
页码：1-33
DOI：10.4086/toc.2018.v014a010
出版社：University of Chicago
摘要：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/loglogn levels of the Sherali–Adams hierarchy (for some constant c > 0) on instances of size n.
关键词：constraint satisfaction problem; convex programming; linear programming