Sherali-Adams integrality gaps matching the log-density threshold
From MaRDI portal
Publication:5009502
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
Cites work
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
- Approximation algorithms and hardness of the \(k\)-route cut problem
- Approximation algorithms for label cover and the log-density threshold
- Concentration of multivariate polynomials and its applications
- Detecting high log-densities, an \(O(n^{1/4})\) approximation for densest \(k\)-subgraph
- ETH hardness for densest-\(k\)-subgraph with perfect completeness
- Graph expansion and the unique games conjecture
- Hardness and approximation for network flow interdiction
- Improved approximation algorithms for label cover problems
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Minimizing the union: tight approximations for small set bipartite vertex expansion
- Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping
- On approximating target set selection
- On the integrality gap of degree-4 sum of squares for planted clique
- Orienteering for electioneering
- Partitioning a graph into small pieces with applications to path transversal
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Public-key cryptography from different assumptions
- Relations between average case complexity and approximation complexity
- Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
- Sum-of-squares Lower Bounds for Planted Clique
- The ordered covering problem
- The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema
- Weighted sums of certain dependent random variables
Cited in
(6)- Tensor clustering with planted structures: statistical optimality and computational limits
- Sum-of-squares lower bounds for densest \(k\)-subgraph
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- scientific article; zbMATH DE number 7561533 (Why is no real title available?)
- Computational barriers to estimation from low-degree polynomials
- Superlinear Integrality Gaps for the Minimum Majority Problem
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)
