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.APPROX-RANDOM.2018.10
URN: urn:nbn:de:0030-drops-94142
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9414/
Go to the corresponding LIPIcs Volume Portal

Chlamtác, Eden ; Manurangsi, Pasin

Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

pdf-format:
LIPIcs-APPROX-RANDOM-2018-10.pdf (0.6 MB)

Abstract

The log-density method is a powerful algorithmic framework which in recent years has given rise to the best-known approximations for a variety of problems, including Densest-k-Subgraph and Small Set Bipartite Vertex Expansion. These approximations have been conjectured to be optimal based on various instantiations of a general conjecture: that it is hard to distinguish a fully random combinatorial structure from one which contains a similar planted sub-structure with the same "log-density".
We bolster this conjecture by showing that in a random hypergraph with edge probability n^{-alpha}, Omega(log n) rounds of Sherali-Adams cannot rule out the existence of a k-subhypergraph with edge density k^{-alpha-o(1)}, for any k and alpha. This holds even when the bound on the objective function is lifted. This gives strong integrality gaps which exactly match the gap in the above distinguishing problems, as well as the best-known approximations, for Densest k-Subgraph, Smallest p-Edge Subgraph, their hypergraph extensions, and Small Set Bipartite Vertex Expansion (or equivalently, Minimum p-Union). Previously, such integrality gaps were known only for Densest k-Subgraph for one specific parameter setting.

BibTeX - Entry

@InProceedings{chlamtc_et_al:LIPIcs:2018:9414,
  author =	{Eden Chlamt{\'a}c and Pasin Manurangsi},
  title =	{{Sherali-Adams Integrality Gaps Matching the Log-Density Threshold}},
  booktitle =	{Approximation, Randomization, and Combinatorial  Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-085-9},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{116},
  editor =	{Eric Blais and Klaus Jansen and Jos{\'e} D. P. Rolim and David Steurer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9414},
  URN =		{urn:nbn:de:0030-drops-94142},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2018.10},
  annote =	{Keywords: Approximation algorithms, integrality gaps, lift-and-project, log-density, Densest k-Subgraph}
}

Keywords: Approximation algorithms, integrality gaps, lift-and-project, log-density, Densest k-Subgraph
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Issue Date: 2018
Date of publication: 13.08.2018

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