Convex relaxations and integrality gaps
From MaRDI portal
Publication:2802523
Recommendations
Cites work
- scientific article; zbMATH DE number 6381632 (Why is no real title available?)
- scientific article; zbMATH DE number 5485464 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2119717 (Why is no real title available?)
- A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A comparison of the Delsarte and Lovász bounds
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Approximate graph coloring by semidefinite programming
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Approximating the independence number via the -function
- CSP gaps and reductions in the lasserre hierarchy
- Coloring -colorable graphs using relatively small palettes
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Edmonds polytopes and a hierarchy of combinatorial problems
- Euclidean distortion and the sparsest cut
- Fast Approximation Algorithms for Knapsack Problems
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Forbidden Intersections
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Improved lower bounds for embeddings into \(L_1\)
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Integrality gaps for Sherali-Adams relaxations
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- Linear degree extractors and the inapproximability of max clique and chromatic number
- Linear programming relaxations of \textsc{maxcut}
- Max CUT and the smallest eigenvalue
- MaxMin allocation via degree lower-bounded arborescences
- New approximation algorithms for graph coloring
- New approximation guarantee for chromatic number
- On distance scales, embeddings, and efficient relaxations of the cut cone
- On the Shannon capacity of a graph
- On the power of unique 2-prover 1-round games
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Proving integrality gaps without knowing the linear program
- Rank bounds and integrality gaps for cutting planes procedures
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- SDP Integrality Gaps with Local ell_1-Embeddability
- Short proofs are narrow—resolution made simple
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Zero knowledge and the chromatic number
Cited in
(30)- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Making the Long Code Shorter
- Lift \& project systems performing on the partial-vertex-cover polytope
- New tools for graph coloring
- Size-degree trade-offs for sums-of-squares and positivstellensatz proofs
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Graphs with large girth and chromatic number are hard for Nullstellensatz
- Relaxation of convex functionals: the gap problem
- The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
- On the hardest problem formulations for the \(0/1\) Lasserre hierarchy
- The power of Sherali-Adams relaxations for general-valued CSPs
- Relaxed outer projections, weighted averages and convex feasibility
- On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy
- Matroid optimization problems with monotone monomials in the objective
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Sum-of-squares bounds via Boolean function analysis
- Superlinear Integrality Gaps for the Minimum Majority Problem
- Bilu-Linial stability, certified algorithms and the independent set problem
- On the hardest problem formulations for the 0/1 Lasserre hierarchy
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Lift-and-project methods for set cover and knapsack
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- A Lasserre lower bound for the min-sum single machine scheduling problem
- A bounded degree SOS hierarchy for polynomial optimization
- Hidden Hamiltonian cycle recovery via linear programming
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Narrow proofs may be maximally long
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
This page was built for publication: Convex relaxations and integrality gaps
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2802523)
