Document Open Access Logo

Sherali-Adams Integrality Gaps Matching the Log-Density Threshold

Authors Eden Chlamtác, Pasin Manurangsi

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2018.10.pdf
  • Filesize: 0.55 MB
  • 19 pages

Document Identifiers

Author Details

Eden Chlamtác
  • Ben-Gurion University, Beer Sheva, Israel
Pasin Manurangsi
  • University of California, Berkeley, USA

Funding

  • Chlamtác, Eden: Partially supported by ISF grant 1002/14.
  • Manurangsi, Pasin: Supported by NSF under Grants No. CCF 1655215 and CCF 1815434.

Cite AsGet BibTex

Eden Chlamtác and Pasin Manurangsi. Sherali-Adams Integrality Gaps Matching the Log-Density Threshold. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.10

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation algorithms
  • integrality gaps
  • lift-and-project
  • log-density
  • Densest k-Subgraph

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein. Inapproximabilty of densest k-subgraph from average case hardness. Unpublished Manuscript, 2011. Google Scholar
  2. Benny Applebaum, Boaz Barak, and Avi Wigderson. Public-key cryptography from different assumptions. In STOC, pages 171-180, 2010. URL: http://dx.doi.org/10.1145/1806689.1806714.
  3. Sanjeev Arora, Boaz Barak, Markus Brunnermeier, and Rong Ge. Computational complexity and information asymmetry in financial products. Commun. ACM, 54(5):101-107, 2011. URL: http://dx.doi.org/10.1145/1941487.1941511.
  4. Pranjal Awasthi, Moses Charikar, Kevin A. Lai, and Andrej Risteski. Label optimal regret bounds for online local learning. In COLT, pages 150-166, 2015. URL: http://jmlr.org/proceedings/papers/v40/Awasthi15a.html.
  5. Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):357-367, 1967. Google Scholar
  6. Boaz Barak, Samuel B. Hopkins, Jonathan Kelner, P. Kothari, Ankur Moitra, and Aaron Potechin. A nearly tight sum-of-squares lower bound for the planted clique problem. In FOCS, pages 428-437, 2016. Google Scholar
  7. Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n^1/4) approximation for densest k-subgraph. In STOC, pages 201-210, 2010. URL: http://dx.doi.org/10.1145/1806689.1806718.
  8. Aditya Bhaskara, Moses Charikar, Aravindan Vijayaraghavan, Venkatesan Guruswami, and Yuan Zhou. Polynomial integrality gaps for strong SDP relaxations of densest k-subgraph. In SODA, pages 388-405, 2012. URL: http://dl.acm.org/citation.cfm?id=2095116.2095150.
  9. Mark Braverman, Young Kun-Ko, Aviad Rubinstein, and Omri Weinstein. ETH hardness for densest-k-subgraph with perfect completeness. In SODA, pages 1326-1341, 2017. Google Scholar
  10. Moses Charikar, MohammadTaghi Hajiaghayi, and Howard J. Karloff. Improved approximation algorithms for label cover problems. Algorithmica, 61(1):190-206, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9464-3.
  11. Moses Charikar, Yonatan Naamad, and Anthony Wirth. On approximating target set selection. In APPROX, pages 4:1-4:16, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.4.
  12. Stephen R. Chestnut and Rico Zenklusen. Hardness and approximation for network flow interdiction. Networks, 69(4):378-387, 2017. URL: http://dx.doi.org/10.1002/net.21739.
  13. Eden Chlamtac, Michael Dinitz, and Robert Krauthgamer. Everywhere-sparse spanners via dense subgraphs. In FOCS, pages 758-767, 2012. URL: http://dx.doi.org/10.1109/FOCS.2012.61.
  14. Eden Chlamtác, Michael Dinitz, and Yury Makarychev. Minimizing the union: Tight approximations for small set bipartite vertex expansion. In SODA, pages 881-899, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.56.
  15. Eden Chlamtác, Pasin Manurangsi, Dana Moshkovitz, and Aravindan Vijayaraghavan. Approximation algorithms for label cover and the log-density threshold. In SODA, pages 900-919, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.57.
  16. Eden Chlamtáč and Pasin Manurangsi. Tight approximations in the semirandom log-density framework via label reduction. In preparation. Google Scholar
  17. Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, and Yuan Zhou. Approximation algorithms and hardness of the k-route cut problem. ACM Trans. Algorithms, 12(1):2:1-2:40, 2016. URL: http://dx.doi.org/10.1145/2644814.
  18. Yash Deshpande and Andrea Montanari. Improved sum-of-squares lower bounds for hidden clique and hidden submatrix problems. In COLT, pages 523-562, 2015. URL: http://jmlr.org/proceedings/papers/v40/Deshpande15.html.
  19. Uriel Feige. Relations between average case complexity and approximation complexity. In STOC, pages 534-543, 2002. URL: http://dx.doi.org/10.1145/509907.509985.
  20. Uriel Feige and Yael Hitron. The ordered covering problem. Algorithmica, Aug 2017. URL: http://dx.doi.org/10.1007/s00453-017-0357-6.
  21. Dima Grigoriev. Linear lower bound on degrees of positivstellensatz calculus proofs for the parity. Theor. Comput. Sci., 259(1-2):613-622, 2001. URL: http://dx.doi.org/10.1016/S0304-3975(00)00157-2.
  22. Mohammad Taghi Hajiaghayi and Kamal Jain. The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. In SODA, pages 631-640, 2006. URL: http://dl.acm.org/citation.cfm?id=1109557.1109626.
  23. Mohammad Taghi Hajiaghayi, Kamal Jain, Lap Chi Lau, Ion I. Mandoiu, Alexander Russell, and Vijay V. Vazirani. Minimum multicolored subgraph problem in multiplex PCR primer set selection and population haplotyping. In ICCS, pages 758-766, 2006. URL: http://dx.doi.org/10.1007/11758525_102.
  24. Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, and Tselil Schramm. On the integrality gap of degree-4 sum of squares for planted clique. In SODA, pages 1079-1095, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch76.
  25. Jonah Kallenbach, Robert Kleinberg, and Scott Duke Kominers. Orienteering for electioneering. Operations Research Letters, 46(2):205-210, 2018. URL: http://dx.doi.org/10.1016/j.orl.2017.10.013.
  26. Subhash Khot. Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J. Comput., 36(4):1025-1071, 2006. URL: http://dx.doi.org/10.1137/S0097539705447037.
  27. Jeong Han Kim and Van H. Vu. Concentration of multivariate polynomials and its applications. Combinatorica, 20(3):417-434, 2000. URL: http://dx.doi.org/10.1007/s004930070014.
  28. Euiwoong Lee. Partitioning a graph into small pieces with applications to path transversal. In SODA, pages 1546-1558, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.101.
  29. Pasin Manurangsi. Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph. In STOC, pages 954-961, 2017. URL: http://dx.doi.org/10.1145/3055399.3055412.
  30. Raghu Meka, Aaron Potechin, and Avi Wigderson. Sum-of-squares lower bounds for planted clique. In STOC, pages 87-96, 2015. URL: http://dx.doi.org/10.1145/2746539.2746600.
  31. Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In STOC, pages 755-764, 2010. URL: http://dx.doi.org/10.1145/1806689.1806792.
  32. Grant Schoenebeck. Linear level lasserre lower bounds for certain k-csps. In FOCS, pages 593-602, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.74.
  33. Hanif D. Sherali and Warren P. Adams. A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math., 3(3):411-430, 1990. URL: http://dx.doi.org/10.1137/0403036.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact