Approximation Algorithms for Machine Scheduling Through Theory and Experiments III

The area of approximation algorithms deals with the design of algorithms for NP-hard optimization problems that provide a guarantee for the quality of the solution returned. Since finding the optimal solution within reasonable time is considered highly unlikely for such problems, one has to settle with alpha-approximate solutions, i.e. solutions that are guaranteed to be within a factor of alpha of the optimum and can be found fast (in polynomial time). In this project we investigate approximation algorithms for classical problems in scheduling theory. By providing the proof of a notable conjecture in the field, we have establishes that one of the oldest and most natural scheduling problems is a special case of the vertex cover problem. This has far-reaching consequences, since one can use the knowledge about vertex cover to readdress this hard combinatorial problem from a new perspective. Further research based on this fact has led to the discovery of a surprising connection to dimension theory of partial orders. This yielded a framework within which all currently best known approximation algorithms can be achieved. Such a framework is particularly attractive, since studying new problems in this family in terms of one of their parameters (their dimension) already gives a promising approach for the design of good approximation algorithms. Research in Approximation Algorithms is two-fold. Besides devising good approximation algorithms, negative results provide valuable information about the approximability of a problem. A negative result shows that an alpha-approximation algorithm (or better) for a specific alpha cannot exists unless NP=P. We provided the first result of this nature for the above problem using recent advances in the field. We will attempt to use our experience and insight in order to extend successful approaches to other problems in scheduling theory. This is particularly interesting, since machine scheduling problems form a family for which understanding the approximability is notoriously intriguing, with many important problems withstanding any progress for several decades. On the other hand, we will address the challenge of understanding what makes certain heuristic approaches succeed or fail in practice. Understanding if some methods are more powerful than others and providing insight regarding the best choice of the parameters of the heuristics will constitute a valuable tool in the quest for algorithms that perform well in practical applications.