Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one

What is it about?

The paper presents an exact algorithm for solving the problem of scheduling a set of jobs on a single machine to maximize total tardiness.

Featured Image

Why is it important?

The allpication of a graphival algorithm turns a pseudo-polynomial standard dynamic programming algorithm into a polynomial one of quadratic complexity.