License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2017.11
URN: urn:nbn:de:0030-drops-75370
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7537/
Go to the corresponding LIPIcs Volume Portal

Ghosh, Mrinalkanti ; Tulsiani, Madhur

From Weak to Strong LP Gaps for All CSPs

pdf-format:
LIPIcs-CCC-2017-11.pdf (0.7 MB)

Abstract

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.

Using our techniques, we also simplify and strengthen the result by Khot et al. [STOC 2014] on (strong) approximation resistance for LPs. They provided a necessary and sufficient condition under which Omega(loglog n) levels of the Sherali-Adams hierarchy cannot achieve an approximation better than a random assignment. We simplify their proof and strengthen the bound to Omega(log(n)/log(log(n))) levels.

BibTeX - Entry

@InProceedings{ghosh_et_al:LIPIcs:2017:7537,
  author =	{Mrinalkanti Ghosh and Madhur Tulsiani},
  title =	{{From Weak to Strong LP Gaps for All CSPs}},
  booktitle =	{32nd Computational Complexity Conference (CCC 2017)},
  pages =	{11:1--11:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-040-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{79},
  editor =	{Ryan O'Donnell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7537},
  URN =		{urn:nbn:de:0030-drops-75370},
  doi =		{10.4230/LIPIcs.CCC.2017.11},
  annote =	{Keywords: Constraint Satisfaction Problem, Convex Programming, Linear Programming Hierarchy, Integrality Gap}
}

Keywords: Constraint Satisfaction Problem, Convex Programming, Linear Programming Hierarchy, Integrality Gap
Collection: 32nd Computational Complexity Conference (CCC 2017)
Issue Date: 2017
Date of publication: 01.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI