Article ID: | iaor2002907 |
Country: | Netherlands |
Volume: | 21 |
Issue: | 5 |
Start Page Number: | 235 |
End Page Number: | 242 |
Publication Date: | Dec 1997 |
Journal: | Operations Research Letters |
Authors: | Tuza Zsolt, Kellerer Hans, Speranza Maria Grazia, Kotov Vladimir |
Keywords: | networks: scheduling |
The partition problem is one of the basic NP-complete problems. While an efficient heuristic for the optimization version, which is equivalent to minimizing the makespan on two identical machines, is known with worst-case ratio