An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
type: Item
instance of: scholarly article
title: An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
zbMATH Open document ID: 1386.90077
author: Adam Kurpisz
author: Samuli Leppänen
author: Monaldo Mastrolilli
published in: Mathematical Programming. Series A. Series B
publication date: 2017-12-01T00:00:00Z
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C22
zbMATH DE Number: 6814720
zbMATH Keywords: sum-of-squares hierarchy
zbMATH Keywords: integrality gap
zbMATH Keywords: min-number of late jobs
MaRDI profile type: Publication
full work available at URL: s10107-016-1102-7
OpenAlex ID: W2570315187
cites work: The Geometry of Scheduling
cites work: Sum of Squares Lower Bounds from Pairwise Independence
cites work: Q5743407
cites work: Q4952606
cites work: Computation of the Lasserre Ranks of Some Polytopes
cites work: A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
cites work: Convex Relaxations and Integrality Gaps
cites work: Complexity of Positivstellensatz proofs for the knapsack
cites work: Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
cites work: Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
cites work: Reducibility among Combinatorial Problems
cites work: Tight Sum-Of-Squares Lower Bounds for Binary Polynomial Optimization Problems.
cites work: On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
cites work: Sum-of-squares hierarchy lower bounds for symmetric formulations
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 Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
cites work: Sum-of-squares Lower Bounds for Planted Clique
cites work: An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
cites work: Approximability and proof complexity
cites work: Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
cites work: Class of global minimum bounds of polynomial functions
cites work: CSP gaps and reductions in the lasserre hierarchy
cites work: Faces for a linear inequality in 0–1 variables
DOI: 10.1007/S10107-016-1102-7
description: scientific article; zbMATH DE number 6814720