A historical note on the complexity of scheduling problems

In 1972 E.M. Livshits and V.I. Rublinetsky published a paper in Russian, in which they presented lineartime 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.(c) 2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).

Automated summary

In 1972, Livshits and Rublinetsky published a paper in Russian where they presented linear time reductions of the partition problem to various scheduling problems. Without knowledge of complexity theory, they argued that if a simple algorithm for the partition problem was not known, then one cannot expect to find simple algorithms for these scheduling problems either. Their work did not receive much recognition, but it was not completely unnoticed. We will describe their approach and review the results.