Sum-of-squares rank upper bounds for matching problems

DOI10.1007/978-3-319-45587-7_35MaRDI QIDQ2835696zbMATH OpenOpenAlexFDO

Authors Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli

Publication date 30 November 2016

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-45587-7_35

zbMATH Keywords

upper boundsmatching problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Sum-of-squares rank upper bounds for matching problems
• The matching problem has no small symmetric SDP
• The matching problem has no small symmetric SDP
• Sherali-Adams relaxations of the matching polytope

Cites work

• 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
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Class of global minimum bounds of polynomial functions
• Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Expressing combinatorial optimization problems by linear programs
• Global optimization with polynomials and the problem of moments
• Integrality gaps of linear and semi-definite programming relaxations for knapsack
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Lower bounds on the size of semidefinite programming relaxations
• On a representation of the matching polytope via semidefinite liftings
• Paths, Trees, and Flowers
• Rank bounds for a hierarchy of Lovász and Schrijver
• Rounding sum-of-squares relaxations
• Sherali-Adams relaxations of the matching polytope
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• The matching problem has no small symmetric SDP
• When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?

Cited in

(1)

• Sum-of-squares rank upper bounds for matching problems

This page was built for publication: Sum-of-squares rank upper bounds for matching problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2835696)