Sherali-Adams integrality gaps matching the log-density threshold

DOI10.4230/LIPICS.APPROX-RANDOM.2018.10MaRDI QIDQ5009502FDOQ5009502

Authors: Eden Chlamtac, Pasin Manurangsi 

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1804.07842

Recommendations

• Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
• Integrality gaps for Sherali-Adams relaxations
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• Approximation schemes via Sherali-Adams hierarchy for dense constraint satisfaction problems and assignment problems
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph

zbMATH Keywords

approximation algorithmsintegrality gapslift-and-projectdensest \(k\)-subgraphlog-density

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Relations between average case complexity and approximation complexity
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Weighted sums of certain dependent random variables
• Public-key cryptography from different assumptions
• Concentration of multivariate polynomials and its applications
• Graph expansion and the unique games conjecture
• Title not available (Why is that?)
• The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
• Improved approximation algorithms for label cover problems
• Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
• Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
• The ordered covering problem
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Sum-of-squares Lower Bounds for Planted Clique
• Partitioning a Graph into Small Pieces with Applications to Path Transversal
• Approximation Algorithms and Hardness of the k -Route Cut Problem
• Hardness and approximation for network flow interdiction
• On Approximating Target Set Selection
• Orienteering for electioneering
• Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion
• Approximation Algorithms for Label Cover and The Log-Density Threshold
• ETH Hardness for Densest-k-Subgraph with Perfect Completeness
• On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique

Cited In (5)

• Tensor clustering with planted structures: statistical optimality and computational limits
• Computational barriers to estimation from low-degree polynomials
• Superlinear Integrality Gaps for the Minimum Majority Problem
• Title not available (Why is that?)
• Sum-of-squares lower bounds for densest \(k\)-subgraph

This page was built for publication: Sherali-Adams integrality gaps matching the log-density threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009502)