il corso sarà tenuto dal Prof. V. T'kindt - University François Rabelais of Tours, France

Combinatorial Optimization consists in determining “optimal” solutions among a set of feasible solutions. Most of hard combinatorial optimization problems are intractable problems in the sense of complexity theory. Consequently, an optimal solution of such problems can only be computed by super polynomial time algorithms. Usually, the evaluation of the efficiency of such algorithms is conducted through extensive computational experiments and the challenge is to solve instances of size as high as possible. But, theoretically speaking, several fundamental questions remain open: for exponential-time algorithms can we establish stronger conclusions than their non polynomiality in time? For instance, is it possible to derive upper bounds on their average complexity or their worst-case complexity? This is a task which is usually performed for polynomially solvable problems: when we provide an exact polynomial-time algorithm we usually also provide information about the number of steps it requires to compute an optimal solution. Why not for NP-hard problems?

Let us consider an exemple. The problem of sorting a collection of n elements is easy and can be done in the worst case, by an algorithm, in O(nlog(n)) steps. Now, consider the knapsack problem which is NP-hard. In the worst case, how many steps could we do to solve the problem? What would be the algorithm? In fact, it can be easily shown that there exists an -exponential- algorithm requiring O(1.41n) to solve the knapsack problem in the worst case. Not so bad!

In that course I will, by means of numerous examples, provide the students with the basics of exponential algorithms: what are the challenges? What are the known technics? What are the results known so far?



CALENDARIO

aula C.

22/10 h 9-13
23/10 h 9-13
26/10 h 9-13
27/10 h 9-13
------------------------------

24/11 : 4h : 10-12, 14-16
25/11 : 2h : 14-16
26/11 : 2h : 10-12
27/11 : 2h : 14-16
28/11 : 4h : 10-12, 14-16
>
9/12 : 2h : 14-16
10/12 : 2h : 14-16
11/12 : 2h : 14-16