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
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.
Recommendations
Cites Work
- scientific article; zbMATH DE number 420868 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1201576 (Why is no real title available?)
- scientific article; zbMATH DE number 1944141 (Why is no real title available?)
- scientific article; zbMATH DE number 1757962 (Why is no real title available?)
- scientific article; zbMATH DE number 2196288 (Why is no real title available?)
- 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
- Compressed polytopes and statistical disclosure limitation
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Decomposition and optimization over cycles in binary matroids
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Master polytopes for cycles of binary matroids
- Matching, Euler tours and the Chinese postman
- On the Shannon capacity of a graph
- On the cycle polytope of a binary matroid
- Semidefinite programming and integer programming
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- The max-cut problem on graphs not contractible to \(K_ 5\)
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 no real title available?)
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)
