Polynomial time approximation algorithms for machine scheduling: ten open problems

Abstract

We discuss what we consider to be the 10 most vexing open questions in the area of polynomial time approximation algorithms for NP-hard deterministic machine scheduling problems. We summarize what is known on these problems, we discuss related results, and we provide pointers to the literature. Copyright © 1999 John Wiley & Sons, Ltd.