A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem

DOI10.1007/978-3-662-48350-3_71zbMath1467.68058arXiv1511.08644OpenAlexW2278496192MaRDI QIDQ3452846

Adam Kurpisz, Monaldo Mastrolilli, Samuli Leppänen

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.08644

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Sum-of-squares hierarchy lower bounds for symmetric formulations, Semidefinite and linear programming integrality gaps for scheduling identical machines

Cites Work

• Unnamed Item
• Global Optimization with Polynomials and the Problem of Moments
• Convex Relaxations and Integrality Gaps
• Sum-of-squares Lower Bounds for Planted Clique
• Sum of Squares Lower Bounds from Pairwise Independence
• Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack
• A Primal-Dual Approximation Algorithm for Min-Sum Single-Machine Scheduling Problems
• On the Hardest Problem Formulations for the $$0/1$$ Lasserre Hierarchy
• Class of global minimum bounds of polynomial functions
• Faces for a linear inequality in 0–1 variables
• CSP gaps and reductions in the lasserre hierarchy
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs
• 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
• Complexity of Positivstellensatz proofs for the knapsack