A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
From MaRDI portal
Publication:3452846
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
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