Few Colors And Short Schedules: The Solutions Of Some Open Problems In Machine Scheduling

The Faculty of Informatics is pleased to announce a seminar given by Monaldo Mastrolilli

DATE: Tuesday, April 23rd 2013
PLACE: USI Università della Svizzera italiana, room A33, Red building (Via G. Buffi 13)
TIME: 16.30

ABSTRACT:
Most combinatorial optimization problems of great practical relevance are NP-hard. The need to cope with these problems is a reason that forces us to relax the notion of optimality and resort to suboptimal approaches: Approximation algorithms compute in polynomial time provably "near-optimal" solutions. NP-hard problems vary greatly in their approximability. A natural question that arises is to understand how close to the optimal solution an approximation algorithm can get in polynomial time. In spite of recent major progress for several combinatorial optimization problems, Schuurman and Woeginger [1], in 1999, emphasized a set of ten prominent open problems in deterministic machine scheduling that have been open for more than two decades by now.
 
In this talk I will survey on some advances on these open problems that I obtained (with other coauthors) and sketch my current research interests.
The first part of the talk is devoted to the study of one the most basic and classical scheduling problem, namely the single machine precedence constrained ordering problem. Despite its fundamental nature the understanding of this problem has been rather weak until recently (see Open Problem n. 9 in [1]). During the talk I'll point out some fascinating connections with the vertex cover problem as well as the dimension theory of partial orders and show how to obtain "short schedules by using few colors". These new insights give the best known approximation algorithms for all the studied variants of the problem and the first (partial) answer to Open Problem n. 9.
 
I continue my talk with Open Problems n. 6 and 7 in [1] about two notorious scheduling problems in shop environments, namely the job shop problem together with the more restricted flow shop problem. We close these open problems by providing stronger inapproximability results that matches the best known approximation algorithm for the general version of flow shops. We give a gap-preserving reduction from graph coloring that relates the chromaticity of the graph with the length of the schedule.
 
In the third part of my talk I will sketch my current research interests in Lift & Projects methods (like the Lasserre hierarchy) that are known to capture the convex relaxations used in the best available approximation algorithms for a wide variety of problems. I will show two recent results emphasizing the strength and the weakness of the Lasserre hierarchy for two problems. I will provide some evidences that this approach might be useful to attack Open Problem 4 in [1].
 
I will conclude my talk with past/present connections and future synergies with the Faculty of Informatics at USI.
 
[1] P. Schuurman and G.J. Woeginger. Polynomial time approximation algorithms for machine scheduling: Ten open problems. Journal of Scheduling 2, 1999, 203--213.

BIO:
Monaldo Mastrolilli is senior researcher at IDSIA-Dalle Molle Institute for Artificial Intelligence and professor at the University of Applied Sciences of Southern Switzerland.

HOST: Prof. Mauro Pezzè