Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Precedence Constrained Scheduling: the solution of some open problems with connections to dimension theory of partial orders

The first part of the seminar is devoted to the single machine scheduling problem to minimize the weighted sum of completion times. I start presenting the solution of a conjecture by Correa & Schulz that implies that the considered scheduling problem is a special case of the minimum weighted vertex cover. It turns out that the vertex cover graph associated with the scheduling problem is exactly the graph of incomparable pairs defined in dimension theory of partial orders. Exploiting this relationship allows us to present a framework for obtaining $(2-2/f)$-approximation algorithms provided that the set of precedence constraints has fractional dimension~$f$. This approach yields the best known approximation ratios for all previously considered classes of precedence constraints we are aware of. The second part of the seminar is devoted to the job shop scheduling problem. Understanding the approximability of the job shop problem is considered one of the most prominent open problems in scheduling theory. Even though the best approximation algorithms have worse than logarithmic performance guarantee, the only known inapproximability result says that it is NP-hard to approximate acyclic job shops within a factor less than~$5/4$. We solve this open problem by presenting almost tight inapproximability results for acyclic job shops and for the generalized version of flow shop.
Type of Seminar:
Optimization and Applications Seminar
Monaldo Mastrolilli
Dec 14, 2009   16:30-18:00

ETH Zentrum, HG G 19.1
Contact Person:

No downloadable files available.
Biographical Sketch: