An Experimental Study of LP-Based Approximation Algorithms for Scheduling Problems.
Martin W. P. SavelsberghR. N. UmaJoel WeinPublished in: INFORMS J. Comput. (2005)
Keyphrases
- approximation algorithms
- scheduling problem
- np hard
- linear programming
- linear program
- primal dual
- optimal solution
- single machine
- special case
- worst case
- minimum cost
- np hardness
- precedence constraints
- quadratic program
- flowshop
- integer programming
- setup times
- lower bound
- vertex cover
- job shop scheduling
- set cover
- processing times
- branch and bound algorithm
- tabu search
- job shop scheduling problem
- facility location problem
- lagrangian relaxation
- approximation ratio
- constraint satisfaction problems
- job shop
- parallel machines
- knapsack problem
- network design problem
- approximation schemes
- disjoint paths
- randomized algorithms
- constant factor approximation
- open shop
- constant factor
- computational complexity
- strongly np hard
- greedy heuristic
- column generation
- convex hull
- metaheuristic