Linear Programming Relaxations and Approximation Algorithms for Scheduling Problems
One important technique in the design of approximation algorithms is to round the optimal solution to a relaxation to obtain a near-optimal solution for the original problem. Although different relaxations have been used, we will mainly focus on linear programming relaxations for a selection of different scheduling problems. The intention is to understand the physics of the LPs in order to design proper rounding techniques, to develop combinatorial algorithms for solving the LPs, and to explore their limit.