Sum-of-Squares Rank Upper Bounds for Matching Problems
From MaRDI portal
Publication:2835696
DOI10.1007/978-3-319-45587-7_35zbMath1452.90271OpenAlexW2517292744MaRDI QIDQ2835696
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
Cites Work
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Rank bounds for a hierarchy of Lovász and Schrijver
- Expressing combinatorial optimization problems by linear programs
- The matching problem has no small symmetric SDP
- Global Optimization with Polynomials and the Problem of Moments
- On a Representation of the Matching Polytope Via Semidefinite Liftings
- Lower Bounds on the Size of Semidefinite Programming Relaxations
- Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
- Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
- Approximate Constraint Satisfaction Requires Large LP Relaxations
- 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
- The Matching Polytope has Exponential Extension Complexity
- Sherali-adams relaxations of the matching polytope
- Rounding sum-of-squares relaxations
- Paths, Trees, and Flowers
- When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
This page was built for publication: Sum-of-Squares Rank Upper Bounds for Matching Problems
