A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
From MaRDI portal
Publication:431017
DOI10.1007/S10107-010-0425-ZzbMATH Open1262.90123OpenAlexW2127671582MaRDI QIDQ431017FDOQ431017
Authors: João Gouveia, Pablo A. Parrilo, Rekha Thomas, Monique Laurent 
Publication date: 26 June 2012
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: The theta bodies of a polynomial ideal are a series of semidefinite programming relaxations of the convex hull of the real variety of the ideal. In this paper we construct the theta bodies of the vanishing ideal of cycles in a binary matroid. Applied to cuts in graphs, this yields a new hierarchy of semidefinite programming relaxations of the cut polytope of the graph. If the binary matroid avoids certain minors we can characterize when the first theta body in the hierarchy equals the cycle polytope of the matroid. Specialized to cuts in graphs, this result solves a problem posed by Lov'asz.
Full work available at URL: https://arxiv.org/abs/0907.4518
Recommendations
semidefinite relaxationscut polytopebinary matroidcutscombinatorial moment matricescycle idealtheta bodies
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Shannon capacity of a graph
- Title not available (Why is that?)
- Matching, Euler tours and the Chinese postman
- Semidefinite programming relaxations for semialgebraic problems
- 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
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Semidefinite representations for finite varieties
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Title not available (Why is that?)
- Title not available (Why is that?)
- Semidefinite programming and integer programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- The max-cut problem on graphs not contractible to \(K_ 5\)
- On the cycle polytope of a binary matroid
- Compressed polytopes and statistical disclosure limitation
- Decomposition and optimization over cycles in binary matroids
- Master polytopes for cycles of binary matroids
- Title not available (Why is that?)
Cited In (16)
- Computation with polynomial equations and inequalities arising in combinatorial optimization
- Matrix convex hulls of free semialgebraic sets
- On the maximum positive semi-definite nullity and the cycle matroid of graphs
- Convex hulls of algebraic sets
- Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
- Tensor theta norms and low rank recovery
- Linear optimization with cones of moments and nonnegative polynomials
- Certifying Polynomial Nonnegativity via Hyperbolic Optimization
- Cycle algebras and polytopes of matroids
- Sums of squares on the hypercube
- Mincut ideals of two-terminal networks
- A semidefinite approach to the $K_i$-cover problem
- Theta rank, levelness, and matroid minors
- Binary Positive Semidefinite Matrices and Associated Integer Polytopes
- Theta bodies for polynomial ideals
- Title not available (Why is that?)
This page was built for publication: A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q431017)
