A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs

DOI10.1007/s10107-010-0425-zzbMath1262.90123arXiv0907.4518OpenAlexW2127671582MaRDI QIDQ431017

João Gouveia, Pablo A. Parrilo, Rekha R. Thomas, Monique Laurent

Publication date: 26 June 2012

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

binary matroidcut polytopesemidefinite relaxationscutscombinatorial moment matricescycle idealtheta bodies

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27)

Related Items

Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies, Sums of squares on the hypercube, A semidefinite approach to the $K_i$-cover problem, Mincut ideals of two-terminal networks, Cycle algebras and polytopes of matroids, Theta rank, levelness, and matroid minors, Matrix convex hulls of free semialgebraic sets, Convex Hulls of Algebraic Sets, Certifying Polynomial Nonnegativity via Hyperbolic Optimization, Tensor theta norms and low rank recovery, Linear optimization with cones of moments and nonnegative polynomials, On Vertices and Facets of Combinatorial 2-Level Polytopes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The max-cut problem on graphs not contractible to \(K_ 5\)
• Semidefinite representations for finite varieties
• Compressed polytopes and statistical disclosure limitation
• On the cycle polytope of a binary matroid
• Decomposition and optimization over cycles in binary matroids
• Semidefinite programming relaxations for semialgebraic problems
• Master polytopes for cycles of binary matroids
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• On the Shannon capacity of a graph
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Matching, Euler tours and the Chinese postman
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope