New Challenges in Scheduling Theory

September, 12-17 2010, Centre CNRS "La Villa Clythia", Frejus

Blocking and hitting problems in chromatic scheduling

SpeakerDominique De Werra

Co-author M.C.Costa (ENSTA. Paris) and Ch.Picouleau (CNAM, Paris).

By definition chromatic scheduling problems are quite often variations and extensions of classical graph coloring instances. Here we shall consider the case which may occur in conflicting situations where an opponent tries to reduce the performance of a scheduler . In particular we will examine the concept of a d-transversal of special sets of vertices or edges like maximum matchings or maximum stable sets in graphs. The d-transversals are subsets (of vertices or of edges) having at least d elements in common with every special set. In a similar way we will define d-blockers as subsets whose deletion reduces the maximum size of special sets by at least d. Connections between these concepts will be exhibited. Classical examples of such concepts will be given (involving cuts, optimal paths, matroids,etc) and we will concentrate on the case of maximum stable sets since these are the basic components of colorings arising in chromatic scheduling instances. Some complexity issues will be discussed and polynomially solvable cases will be outlined.