Convex relaxations and integrality gaps
From MaRDI portal
Publication:2802523
DOI10.1007/978-1-4614-0769-0_6zbMATH Open1334.90099OpenAlexW129224317MaRDI QIDQ2802523FDOQ2802523
Authors: Eden Chlamtac, Madhur Tulsiani 
Publication date: 26 April 2016
Published in: International Series in Operations Research & Management Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-1-4614-0769-0_6
Recommendations
Combinatorial optimization (90C27) Semidefinite programming (90C22) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)
Cites Work
- Forbidden Intersections
- Approximate graph coloring by semidefinite programming
- On the Shannon capacity of a graph
- Linear degree extractors and the inapproximability of max clique and chromatic number
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Fast Approximation Algorithms for Knapsack Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- 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
- The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- New approximation algorithms for graph coloring
- A comparison of the Delsarte and Lovász bounds
- Linear programming relaxations of \textsc{maxcut}
- Proving integrality gaps without knowing the linear program
- Title not available (Why is that?)
- Title not available (Why is that?)
- Integrality gaps for Sherali-Adams relaxations
- Edmonds polytopes and a hierarchy of combinatorial problems
- Title not available (Why is that?)
- Zero knowledge and the chromatic number
- Short proofs are narrow—resolution made simple
- Euclidean distortion and the sparsest cut
- Approximating the independence number via the \(\vartheta\)-function
- New approximation guarantee for chromatic number
- On distance scales, embeddings, and efficient relaxations of the cut cone
- Improved lower bounds for embeddings into \(L_1\)
- MaxMin allocation via degree lower-bounded arborescences
- Rank bounds and integrality gaps for cutting planes procedures
- Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
- Max CUT and the smallest eigenvalue
- Integrality gaps of \(2-o(1)\) for vertex cover SDPs in the Lovász-Schrijver hierarchy
- Coloring -colorable graphs using relatively small palettes
- Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
- CSP gaps and reductions in the lasserre hierarchy
- Approximating coloring and maximum independent sets in 3-uniform hypergraphs
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- Optimal Sherali-Adams Gaps from Pairwise Independence
- Title not available (Why is that?)
- Integrality gaps for sparsest cut and minimum linear arrangement problems
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- SDP Integrality Gaps with Local ell_1-Embeddability
Cited In (30)
- 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
- Sum-of-squares bounds via Boolean function analysis
- Quasi-PTAS for scheduling with precedences using LP hierarchies
- Matroid optimization problems with monotone monomials in the objective
- 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
- Title not available (Why is that?)
- Lift-and-project methods for set cover and knapsack
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- A Lasserre lower bound for the min-sum single machine scheduling problem
- A bounded degree SOS hierarchy for polynomial optimization
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- Hidden Hamiltonian cycle recovery via linear programming
- Semidefinite and linear programming integrality gaps for scheduling identical machines
- Narrow proofs may be maximally long
- Polynomial integrality gaps for strong SDP relaxations of densest \(k\)-subgraph
- Bounding the gap between the McCormick relaxation and the convex hull for bilinear functions
- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
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)
