Approximation Algorithms for Machine Scheduling Through Theory and Experiments

The two main goals of the project are the following: Approximation Algorithms: We want to address and possibly solve some of the open questions in scheduling theory which have been open for more than 20 years by now. As Schuurman and Woeginger write “Progress on any of them would be very important” and “it will trigger several breakthroughs in the near future”. Understanding Heuristic Methods: many heuristics for several problems have no worst-case guarantees on performance, but do well for “typical” problems. Understanding when and to what extent heuristic methods succeed and fail is a challenge for both theory and practice. We would like to obtain a theoretical understanding of when widely used heuristics, like Ant Colony Optimization and Tabu Search succeed.