Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines
From MaRDI portal
Publication:3186499
DOI10.1007/978-3-319-33461-5_13zbMath1402.90054OpenAlexW2467099678MaRDI QIDQ3186499
Andreas Wiese, Víctor Verdugo, Claire Mathieu, Monaldo Mastrolilli, Adam Kurpisz, Tobias Mömke
Publication date: 10 August 2016
Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-33461-5_13
Semidefinite programming (90C22) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the configuration-LP for scheduling on unrelated machines
- Semidefinite programming relaxations for semialgebraic problems
- Global Optimization with Polynomials and the Problem of Moments
- Convex Relaxations and Integrality Gaps
- Lift-and-Project Methods for Set Cover and Knapsack
- The Design of Approximation Algorithms
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Lasserre Lower Bound for the Min-Sum Single Machine Scheduling Problem
- Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy
- Approximating Sparsest Cut in Graphs of Bounded Treewidth
- The Operator $\Psi$ for the Chromatic Number of a Graph
- Cones of Matrices and Set-Functions and 0–1 Optimization
- `` Strong NP-Completeness Results
- The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
- Approximating independent sets in sparse graphs
- Integrality Gaps of $2-o(1)$ for Vertex Cover SDPs in the Lovász–Schrijver Hierarchy
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
This page was built for publication: Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines
