**Sujet de thèse: **Graph algorithms to handle job scheduling problems

**Directeurs
de thèse **:M. Montassier, A.
Pêcher (HDR) , A. Raspaud

**Courriels **:montassi@labri.fr, pecher@labri.fr, raspaud@labri.fr

**Équipe**: combinatoire et algorithmique

**Description
synthétique du sujet (en anglais)**

A breakthrough was
recently achieved by Fekete and Schepers (2004) to model multi-dimensional
placements: instead of defining the absolute position of items, they formulated
the problem in terms of the relative positions of items. Two items have non
overlapping positions if they are on each others side along at least one
dimension. This is modeled by defining a non-edge in a graph associated to that
dimension: thus this graph is the complement of an interval graph. This model
is very efficient as any symmetric placement gives rise to the same graph
representation.

The aim is to develop efficient algorithms to handle periodic scheduling
problems, as cyclic orthogonal packings can be used to handle periodic
scheduling problems: in the cyclic orthogonal packing problem, boundaries of
the container are identified two-by-two. Hence using the similar approach gives
now the complement of a circular arc graph for each dimension, which are not
perfect anymore. Thus Fekete and Schepers' approach stops short...

Hence specific graph colorings algorithms are needed: circular colorings are
well-known to be relevant when periodic solutions are required. Two new kinds
of graph colorings, called adapted coloring (introduced by Hell and Zhu) and
adapted list coloring (introduced by Kostochka and Zhu) are also suitable to
handle scheduling problems. The aim is to better understand these new
colorings, and their relationships with scheduling problems.

The research will be conducted within LaBRI's subteam "Graphs and
applications" http://dept-info.labri.fr/graphes/ and within INRIA team RealOpt
http://realopt.math.cnrs.fr/

**Description
détaillée du sujet (en anglais):**

Many combinatorial optimization problems can be modeled as the search for a speciﬁc structure in a graph: for example ensuring connectivity in a network amounts to building a tree that spans all the nodes; inquiring about its resistance to failure amounts to searching for a minimum cardininality cut that partitions the graph; selecting disjoint pairs of objects is represented by a so called matching; disjunctive choices can be modeled by edges in a so called conﬂict graph where one searches for stable sets; in particular, in time tabling problems, the conﬂict graph is a so called interval graph (recognizing this special property leads to an easy solution).

The relationships between both mathematical programming and graph theory have allowed several famous research advances such as perfect graph theory and its implications in semidefinite programming [7], Goemans-Williamson Max Cut algorithm [6], Edmond’s work on the matching polytope [5], paving the way for efﬁcients algorithm to compute the weighted stability number of claw-free graphs ... Let us develop one such example, which lies at the heart of this subject.

Fekete and Schepers [4] managed a recent breakthrough in solving multi-dimensional orthogonal placement problems. by using an efﬁcient representation of all geometrically symmetric solutions by a so called packing class involving one interval graph (whose complement admits a transitive orientation: each such orientation of the edges corresponds to a speciﬁc placement of the forms) for each dimension. Though Fekete & Schepers’ framework is very efﬁcient, we have however identiﬁed several weaknesses in their algorithms: the most obvious one is that they do not take advantage of the sophisticated data structures (called MPQ trees) which were introduced to design linear time recognition algorithms of interval graphs. They use instead a very basic characterization of interval graphs. Thus we think that signiﬁcative improvments on this problems are possible. This will be the ﬁrst goal.

Another goal will
be to apply the same approach to handle scheduling problems: Fekete and
Schepers’ reformulation in this setting would involve circular-arc graphs. In
contrary to interval graphs, these graphs are not perfect and relevant
algorithms are to be designed. This is one topic of the subject. Some of the
other topics rely on variations of chromatic number, able to capture more
precisely the speciﬁcity of some subproblems of packing problems. The
concept of adapted colouring of graph was introduced by Hell and Zhu [9], and
has connections with matrix partition of graphs, graph homomorphisms, and full
constraint satisfaction problems

[1, 2, 3, 8]. Adapted list colouring of graphs and hypergraphs was introduced
by Kostochka and Zhu in [10]. Let us explain in a few word why adapted list
colouring, for instance, is suitable to modelize scheduling problems. Compared
to the original list colouring model, the adapted list colouring allows
different constraints for different colours. For example, suppose there is a
set of football games needed to be scheduled into a set of time slots. The time
slots are the colours. The constraints are whether two games can be assigned to
the same time slot. For external reasons, it may happen that two games a and b
cannot be both assigned to time slot i, however, they can be both assigned to
time slot j. Adapted list coloring allows to take into account this kind of
constraints.

Channel assignment is another well-known application area of graph
colorings.
The channel assignment problem in radio or cellular phone networks is
the
following : we need to assign radio frequency bands to transmitters
(each station
gets one channel which corresponds to an integer). In order to avoid
interference, if two stations are very close, then the separation of
the
channels assigned to them has to be large enough. Moreover, if two
stations are
close (but not very close), then they must also receive channels that
are
sufﬁciently far apart. Such a problem may be modelled by L(p,
q)-labellings of a graph G. The vertices of this graph correspond to
the
transmitters and two vertices are linked by an edge if they are very
close. Two
vertices are then considered close if they are at distance 2 in the
graph. Let dist(u,v) denote the distance between the two vertices u and
v. An L(p,
q)-labelling of G is an integer assignment f to the vertex set V (G)
such that:

• |f (u) − f (v)| ≥ p, if dist(u,v) = 1;

• |f (u) − f (v)| ≥ q, if dist(u,v) = 2.

As the separation between channels assigned to vertices at distance 2 cannot be smaller than the separation between channels assigned to vertices at distance 1, it is often assumed that p ≥ q. The span of f is the difference between the largest and the smallest labels of f plus one. The λ - number of G is the minimum span over all L(p, q)-labellings of G. Moreover, very often, because of technical reasons or dynamicity, the set of channels available varies from transmitter to transmitter. Therefore one has to consider the list version of L(p, q)-labellings. A k-list-assignment L of a graph is a function which assigns to each vertex v of the graph a list L(v) of k prescribed integers. Given a graph G, the list λ -number, denoted λl(G) is the smallest integer k such that, for every k-list-assignment L of G, there exists an L(p, q)-labelling f such that f (v) ∈ L(v) for every vertex v. Surprisingly, list L(p, q)-labellings have been studied only very little explicitely and seems to appear only very recently in the literature. However, some of the proofs for L(p, q)- labellings also work for list L(p, q)-labellings. Generalisations of L(p, q)-labellings in which for each i ≥ 1, a minimum gap of pi is required for channels assigned to vertices at distance i, have also been studied [11, 12]. In this PhD, these new trends of graph colorings w.r.t. channel assignment will be studied.

Hence there are basically two main aims: the ﬁrst one is to improve Fekete & Schepers’ framework for the orthogonal multidimensional knapsack problem, as depicted in Goals 1 & 2 below; the second one is to extend Fekete & Scheper’s framework to handle job scheduling problems, and more generally investigate variations of graph colorings to handle problems from discrete optimization, such as frequency assignment problems.

• Goal 1: improve Fekete & Schepers’ algorithm to decide whether a set of items ﬁts together in a container, by using more powerful characterizations of interval graphs such as PQ trees.

Task 1: give efﬁcient combinatorial algorithms with the help of graph algorithms related to interval graphs

· Task 2: give new linear-programming formulations and evaluate the associate bounds

· Task 3: improve every algorithms/formulations by breaking symmetry issues

· Task 4: evaluate every algorithms/formulations from Tasks 1,2 (+3) against public benchmarks

• Goal 2: comparison to other enumeration schemes for the orthogonal knapsack problem.

· Task 5: implement enumeration scheme of Fekete & Schepers (2004)

· Task 6: implement reduction scheme of Clautiaux & al (2005)

· Task 7: improve algorithms from Task 5 and 6 by breaking symmetry issues

• Goal 3: obtain new relevant results in graph colorings related to the job scheduling problem, frequency assignment and network design.

· Task 8 (periodic scheduling): exhibit suitable structural properties of circular-arc graphs in order to design an analogous framework to Fekete & Schepers’ for the periodic scheduling problem. Investigate circular-coloring and adapted coloring for the periodic scheduling problem.

Task 9 (frequency assignment): study new trends of graph colorings such as list L(p, q)-labellings to handle frequency assignment problems

**References:**

[1] T. Feder and P. Hell. Full constraint satisfaction problems. SIAM J. Comput., 36:230–246, 2006.

[2] T. Feder, P. Hell, S. Klein, and R. Motwani. Complexity of list partitions.
SIAM J. Discrete Math.,

16:449–478, 2003.

[3] T. Feder, P. Hell, D. Kral, and J. Sgall. Two algorithms for list matrix
partition. Proc. 16th Annual

ACM-SIAM Symposium on Discrete Algorithms (SODA) 870–876, 2005.

[4] S.P. Fekete and J. Schepers. A combinatorial characterization of
higher-dimensional orthogonal

packing. Mathematics of Operations Research, 29:353–368, 2004.

[5] J.E. Edmonds Maximum Matching and a Polyhedron with (0,1) Vertices J. Res.
Nat. Bur. Stan-

dards, 69:125–130, 1965

[6] M.X. Goemans and D.P. Williamson Improved approximation algorithms for
Maximum Cut and

Satisﬁability problems using semideﬁnite programming Journal of
the ACM, 42:1115–1145, 1995

[7] M. Grotschel, L. Lovasz, and A. Schrijver. Geometric Algorithms and
Combinatorial Optimization.

Springer Verlag, 1988.

000

[8] P. Hell and J. Nesetril. Graphs and homomorphisms. Oxford University Press, 2004.

[9] P. Hell and X. Zhu. Adaptable chromatic number of graphs. European J.
Combinatorics, to appear.

[10] A. Kostochka and X.Zhu. Adapted list coloring of graphs and hypergraphs.
SIAM J. Discrete

Math., to appear.

[11] D. Kral Channel assignment problem with variable weights. SIAM J. Discrete Math. 20:690–704,

2006.

[12] D. D.-F. Liu and X. Zhu. Multilevel distance labelings for paths and
cycles. SIAM J. Discrete Math.

19:610–621, 2005.