On the optimality of exact and approximation algorithms for scheduling problems.
Lin ChenKlaus JansenGuochuan ZhangPublished in: J. Comput. Syst. Sci. (2018)
Keyphrases
- approximation algorithms
- scheduling problem
- np hard
- optimal solution
- precedence constraints
- special case
- worst case
- flowshop
- single machine
- vertex cover
- facility location problem
- set cover
- minimum cost
- branch and bound algorithm
- strongly np hard
- np hardness
- processing times
- randomized algorithms
- job shop
- open shop
- exact algorithms
- job shop scheduling problem
- primal dual
- integer programming
- parallel machines
- job shop scheduling
- constraint satisfaction problems
- lower bound
- approximation ratio
- combinatorial auctions
- approximation schemes
- constant factor approximation
- setup times
- exact solution
- knapsack problem
- computational complexity
- approximation guarantees
- network design problem
- traveling salesman problem
- linear program
- tabu search