ABSTRACT
In this chapter we show how to develop and analyze polynomial-time approximation algorithms with performance guarantees for scheduling problems. For a problem which is classified as NP-complete, several approaches may be used in order to propose an optimal solution or a solution close to the optimum. When looking at an optimal solution, we may recall the three classical exact methods: branch and bound, branch and cut, and dynamic programming.
