Convex Relaxations and Integrality Gaps

DOI10.1007/978-1-4614-0769-0_6zbMath1334.90099OpenAlexW129224317MaRDI QIDQ2802523

Eden Chlamtáč, 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

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (28)

Narrow Proofs May Be Maximally Long ⋮ On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy ⋮ Making the Long Code Shorter ⋮ A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem ⋮ Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials ⋮ On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy ⋮ Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines ⋮ A bounded degree SOS hierarchy for polynomial optimization ⋮ On the Lovász Theta Function for Independent Sets in Sparse Graphs ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Unnamed Item ⋮ On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy ⋮ Hidden Hamiltonian Cycle Recovery via Linear Programming ⋮ Quasi-PTAS for scheduling with precedences using LP hierarchies ⋮ Lift \& project systems performing on the partial-vertex-cover polytope ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Lift-and-project methods for set cover and knapsack ⋮ Semidefinite and linear programming integrality gaps for scheduling identical machines ⋮ New Tools for Graph Coloring ⋮ Size-degree trade-offs for sums-of-squares and positivstellensatz proofs ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ Unnamed Item ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
• Zero knowledge and the chromatic number
• Approximating the independence number via the \(\vartheta\)-function
• Edmonds polytopes and a hierarchy of combinatorial problems
• New approximation guarantee for chromatic number
• Integrality gaps for sparsest cut and minimum linear arrangement problems
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
• On the power of unique 2-prover 1-round games
• Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Optimal Sherali-Adams Gaps from Pairwise Independence
• Robust Algorithms for on Minor-Free Graphs Based on the Sherali-Adams Hierarchy
• Improved Lower Bounds for Embeddings into $L_1$
• Forbidden Intersections
• Approximate graph coloring by semidefinite programming
• Fast Approximation Algorithms for Knapsack Problems
• A comparison of the Delsarte and Lovász bounds
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• On the Shannon capacity of a graph
• New approximation algorithms for graph coloring
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The Lovász Theta Function and a Semidefinite Programming Relaxation of Vertex Cover
• Short proofs are narrow—resolution made simple
• Coloring -colorable graphs using relatively small palettes
• A $(\log n)^{\Omega(1)}$ Integrality Gap for the Sparsest Cut SDP
• SDP Integrality Gaps with Local ell_1-Embeddability
• Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES
• Max cut and the smallest eigenvalue
• Integrality gaps for Sherali-Adams relaxations
• CSP gaps and reductions in the lasserre hierarchy
• MaxMin allocation via degree lower-bounded arborescences
• Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
• Euclidean distortion and the sparsest cut
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming

This page was built for publication: Convex Relaxations and Integrality Gaps