Semidefinite and linear programming integrality gaps for scheduling identical machines

DOI10.1007/s10107-017-1152-5zbMath1402.90055OpenAlexW2612425202MaRDI QIDQ1800998

Andreas Wiese, Tobias Mömke, Claire Mathieu, Monaldo Mastrolilli, Adam Kurpisz, Víctor Verdugo

Publication date: 26 October 2018

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-017-1152-5

zbMATH Keywords

configuration LPidentical machine schedulingLovász-SchrijverSherali-Adams

Mathematics Subject Classification ID

Semidefinite programming (90C22) Linear programming (90C05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (2)

Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ Superlinear Integrality Gaps for the Minimum Majority Problem

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
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• 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
• The Operator $\Psi$ for the Chromatic Number of a Graph
• Cones of Matrices and Set-Functions and 0–1 Optimization
• `` Strong NP-Completeness Results
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set
• Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
• 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
• Expander flows, geometric embeddings and graph partitioning

This page was built for publication: Semidefinite and linear programming integrality gaps for scheduling identical machines