A 1.47-approximation algorithm for a preemptive single-machine scheduling problem.

Michel X. Goemans Joel Wein David P. Williamson

Published in: Oper. Res. Lett. (2000)

Keyphrases

single machine scheduling problem
dynamic programming
optimization algorithm
cost function
optimal solution
objective function
computational complexity
search space
np hard
database systems
multi objective
worst case
branch and bound algorithm
knapsack problem