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

DOI10.1007/S10107-010-0425-ZzbMATH Open1262.90123arXiv0907.4518OpenAlexW2127671582MaRDI 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

• Theta bodies for polynomial ideals
• On a positive semidefinite relaxation of the cut polytope
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• scientific article; zbMATH DE number 2196288
• Block-diagonal semidefinite programming hierarchies for 0/1 programming

zbMATH Keywords

semidefinite relaxationscut polytopebinary matroidcutscombinatorial moment matricescycle idealtheta bodies

Mathematics Subject Classification ID

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

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 (18)

• 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
• Equivariant Semidefinite Lifts and Sum-of-Squares Hierarchies
• Tensor theta norms and low rank recovery
• Convex Hulls of Algebraic Sets
• 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
• Optimal homologous cycles, total unimodularity, and linear programming
• Theta rank, levelness, and matroid minors
• On Vertices and Facets of Combinatorial 2-Level Polytopes
• 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)