Sum-of-squares rank upper bounds for matching problems
type: Item
instance of: scholarly article
title: Sum-of-squares rank upper bounds for matching problems
zbMATH Open document ID: 1412.90131
author: Adam Kurpisz
author: Samuli Leppänen
author: Monaldo Mastrolilli
published in: Journal of Combinatorial Optimization
publication date: 2018-12-06T00:00:00Z
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 6990032
zbMATH Keywords: sum-of-squares hierarchy
zbMATH Keywords: integrality gap
zbMATH Keywords: matching problem
MaRDI profile type: Publication
full work available at URL: s10878-017-0169-2
OpenAlex ID: W2751975837
cites work: Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
cites work: Rounding sum-of-squares relaxations
cites work: The matching problem has no small symmetric SDP
cites work: Approximate Constraint Satisfaction Requires Large LP Relaxations
cites work: Paths, Trees, and Flowers
cites work: Sparse sums of squares on finite abelian groups and improved semidefinite lifts
cites work: When Does the Positive Semidefiniteness Constraint Help in Lifting Procedures?
cites work: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
cites work: Q4902474
cites work: Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
cites work: On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
cites work: Global optimization with polynomials and the problem of moments
cites work: A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
cites work: Lower Bounds on the Size of Semidefinite Programming Relaxations
cites work: Cones of Matrices and Set-Functions and 0–1 Optimization
cites work: Sherali-adams relaxations of the matching polytope
cites work: Approximability and proof complexity
cites work: The Matching Polytope has Exponential Extension Complexity
cites work: A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
cites work: Class of global minimum bounds of polynomial functions
cites work: On a representation of the matching polytope via semidefinite liftings
cites work: Rank bounds for a hierarchy of Lovász and Schrijver
cites work: Expressing combinatorial optimization problems by linear programs
DOI: 10.1007/S10878-017-0169-2
description: scientific article; zbMATH DE number 6990032