A historical note on the complexity of scheduling problems

Abstrakt

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/).

Klíčová slova

• Partition
• Scheduling
• Computational complexity
• NP-hardness