Semidefinite and linear programming integrality gaps for scheduling identical machines.
Adam KurpiszMonaldo MastrolilliClaire MathieuTobias MömkeVictor VerdugoAndreas WiesePublished in: Math. Program. (2018)
Keyphrases
- identical machines
- semidefinite
- linear programming
- semidefinite programming
- interior point methods
- processing times
- linear programming relaxation
- scheduling problem
- single machine
- linear program
- extreme points
- lp relaxation
- primal dual
- feasible solution
- np hard
- mixed integer
- integer programming
- dynamic programming
- objective function
- precedence constraints
- column generation
- polynomial time approximation
- quadratic programming
- sufficient conditions
- setup times
- linear systems
- higher dimensional
- lagrangian relaxation
- optimal solution