2023-01-02
A historical note on the complexity of scheduling problems
Publication
Publication
Operations Research Letters , Volume 51 - Issue 1 p. 1- 2
In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented linear-time reductions of the partition problem to a number of scheduling problems. Unaware of complexity theory, they argued that, since partition is not known to have a simple algorithm, one cannot expect to find simple algorithms for these scheduling problems either. Their work did not go completely unnoticed, but it received little recognition. We describe the approach and review the results.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1016/j.orl.2022.11.006 | |
| Operations Research Letters | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Lenstra, J. K., Strusevich, V., & Vlach, M. (2023). A historical note on the complexity of scheduling problems. Operations Research Letters, 51(1), 1–2. doi:10.1016/j.orl.2022.11.006 |
|
