Sum-of-squares rank upper bounds for matching problems
From MaRDI portal
Publication:2835696
DOI10.1007/978-3-319-45587-7_35zbMATH Open1452.90271OpenAlexW2517292744MaRDI QIDQ2835696FDOQ2835696
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
Recommendations
Cites Work
- Global optimization with polynomials and the problem of moments
- Paths, Trees, and Flowers
- Expressing combinatorial optimization problems by linear programs
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Class of global minimum bounds of polynomial functions
- 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
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- Sherali-Adams relaxations of the matching polytope
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Lower bounds on the size of semidefinite programming relaxations
- On a representation of the matching polytope via semidefinite liftings
- Rank bounds for a hierarchy of Lovász and Schrijver
- Rounding sum-of-squares relaxations
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
- Integrality gaps of linear and semi-definite programming relaxations for knapsack
- The matching problem has no small symmetric SDP
Cited In (1)
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)
