Sum-of-squares rank upper bounds for matching problems
From MaRDI portal
Publication:1631641
DOI10.1007/S10878-017-0169-2zbMath1412.90131OpenAlexW2751975837MaRDI QIDQ1631641
Adam Kurpisz, Samuli Leppänen, Monaldo Mastrolilli
Publication date: 6 December 2018
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-017-0169-2
Cites Work
- Unnamed Item
- 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
- 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
- On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
- Class of global minimum bounds of polynomial functions
- Cones of Matrices and Set-Functions and 0–1 Optimization
- The matching problem has no small symmetric SDP
- 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
- Approximability and proof complexity
- 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
