General Techniques for Combinatorial Approximation

This is a tutorial on general techniques for combinatorial approximation. In addition to covering known techniques, a new one is presented. These techniques generate fully polynomial time approximation schemes for a large number of NP-complete problems. Some of the problems they apply to are: 0-1 knapsack, integer knapsack, job sequencing with deadlines, minimizing weighted mean flow times, and optimal SPT schedules. We also present experimental results for the job sequencing with deadlines problem.