PERIODO: GENNAIO - FEBBRAIO 2018

Il corso sarà tenuto dal prof Marc DAMAGE della RMIT University - Melbourne

Graphs are a concept of discrete mathematics aiming to represent links between pair of objects. The set of “objects” is the vertex (or node) set and two objects in relation are linked by an edge. The relation can be non-symmetric (``Alice is Bob’s manager’’), corresponding to a directed edge or symmetric (“Alice and Bob are in the same department”), corresponding to an undirected edge. They appear as an essential tool in particular for the analysis of decision problems aiming to find an optimal organisation, thus for many problems in management science. The related topic in called graph optimisation. All kind of networks (transportation, communication, social …) are very natural examples of graphs. This course aims to illustrate some basic technics in graph optimisation: based on few typical examples we will discuss optimisation problems and their optimality conditions, algorithms and their analysis as well as how such abstract models allow to link problems that are a priori completely different.

After a brief introduction of the concepts, we will first consider the question of “reachability” which is one of the most natural question arising when dealing with a network. The first question for instance whether two vertices are connected in the network, leading various notions of connectivity, trees and paths. We will analyse in particular the minimum spanning tree problem and prove that a greedy algorithm finds an optimal solution as well as the optimal path problem that illustrates dynamic programming. These problems appear for instance in logistics and network design.

In a second part we will focus on scheduling problems and their relation with graph theory. The first problem we will discuss is the case with only precedence constraints between tasks (“task A needs to be completed before B starts”). We will show that this problem is actually an optimal path problem in the “job-on-node model” and will deduce in particular the Critical Path Method (CPM). It will give us the occasion to discuss a linear programming approach and compare it with a pure combinatorial approach. Then, we will discuss disjunctive constraints (“A and B cannot be performed in the same time”) and how they induce additional hardness in the model. This will lead us to graph colouring problems: the objective is assign colours to vertices such that adjacent vertices are not of the same colour and the number of colours is minimised. We will discuss various models in different graph classes including interval graphs, permutation graphs and overlaps graphs. The models we will discuss arise, for instance, in optimal booking systems, railway optimisation or stacking problems. This will give us the opportunity to discuss the complexity of graph colouring in different cases.

Timetable (the course will take place in classroom B of DIGEP):
Tuesday January 9, 15.00-18.00
Thursday January 11, 09.00-12.00
Friday January 12, 14.30-17.30
Monday January 15, 09.00-12.00
Wednesday January 17, 09.00-12.00
Thursday January 18, 14.30-17.30
Friday January 19, 14.30-16.30

For further enquiries, please contact F. Della Croce (federico.dellacroce@polito.it)