1
$\begingroup$

I am planning to teach approximation algorithms for problems such as job scheduling and number partitioning. I would like to teach proofs, but the proofs I found in the original papers (e.g. this one) are quite hard to understand - they use complicated weighting schcemes, and there is no explanation of how these particular weights were derived.

I am looking for a textbook (or an article) that explains these proofs in a more 'didactic' way, that is, the proof is developed step by step, such that the reader can understand how the proof was derived, and use this understanding to develop similar proofs.

What is a good textbook for this topic?

$\endgroup$
1
  • $\begingroup$ The textbook "Introduction to Scheduling" (doi.org/10.1201/9781420072747), by Yves Robert and Frederic Vivien, is a good place to start (for the scheduling part). Not posting this as an answer as I no longer have access to a copy, and this is just based on a memory that it contains what you're looking for. $\endgroup$
    – integrator
    Oct 1 at 14:47
1
$\begingroup$

The textbook The design of approximation algorithms by Williamson and Shmoys covers many different scheduling and partition problems, and they do so with proofs that are quite accessible.

$\endgroup$
1
  • $\begingroup$ Looks great, thanks $\endgroup$ Nov 1 at 14:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.