Séminaires 2003 - 2004

1er juillet 2004	Michael Lomonosov (Beer Sheva)	Local patterns of paths packings
03 juin 2004	Laurent Vuillon (Chambéry)	Mots de coupures dans un pavage régulier
27 mai 2004	Michael Tarsi (Israël)	The Lonely Runner Problem
27 mai 2004	Zoltán Szigeti (Paris 6)	On well-balanced orientation of graphs
29 janvier 2004	Etienne Birmelé (Lyon 1)	Largeur d'arborescence

1er juillet 2004 : Michael Lomonosov (Beer Sheva) : Local patterns of paths packings.

Caratheodory Bounds and the Cutting Stock Problem We consider some issues related to the cutting stock problem. The cutting stock problem is the following: Given a demand on d item types, each type i in {1, 2, . . . , d} characterised by the size ai common for all items of this type and the number bi of items of this type, find the minimum number of stocks of length ? needed to cut all these items. The integer program due to Gilmore and Gomory includes exponentially many variables. However, it is possible to show that one can provide a solution of polynomial size, thus the decision version of the problem (ÒIs there a cutting using m stocksÓ) is NP-complete. For the cutting stock problem with a fixed number d of different item sizes only fixed number of nonzero variables are required. The Gilmore-Gomory integer program has the very strong linear pro- gramming relaxation. In fact, no instance is known with the gap between the integer optimum value and the optimum value of the linear programming relaxation achieving 2, and it was conjectured that the cutting stock problem has the modified integer rounding-up (MIRU) property, that is, the integer optimum value is at most + 1. where LIN is the optimum value of the corresponding linear programming relaxation. We prove the property for some particular classes of the cutting stock problem.

03 juin 2004 : Laurent Vuillon (Chambéry) : Mots de coupures dans un pavage régulier.

Dans ce travail en collaboration avec P. Hubert (IML, Marseille), nous montrons que la complexité d'un mot de coupures u dans un pavage régulier par un polyomino Q est égale à Pn(u)=(p+q-1)n +1, pour tout n > 0 où Pn(u) compte le nombre de facteurs distincts de longueur n du mot infini u et où le mot de contour du polyomino Q est donné par 2p segments horizontaux et 2q segments verticaux. Nous reviendrons dans cet exposé sur le théorème de Beauquier-Nivat donnant une caractérisation par mots de contour des polyominos qui pavent le plan par translations.

27 mai 2004 : Zoltán Szigeti (Paris 6) : On well-balanced orientation of graphs.

We shall consider orientation problems of graphs concerning edge-connectivity requirements. I will explain Nash-Williams' well-balanced orientation theorem. Generalizations, applications and counter-examples for related problems will also be presented.

29 janvier 2004 : Etienne Birmelé (Lyon 1) : Largeur d'arborescence.

Robertson et Seymour ont introduit la largeur d'arborescence qui est un outil très puissant pour l'étude de graphes, tant d'un point de vue théorique qu'algorithmique. Ils ont entre autres montré qu'une famille F de graphes est de largeur d'arborescence bornée si et seulement si il existe un graphe planaire qui n'est mineur d'aucun élément de F. Cependant, leur borne est doublement exponentielle en la taille du mineur interdit. Après avoir introduit la largeur d'arborescence, nous présenterons plusieurs manières de la considérer et montrerons comment elles permettent de trouver une borne polynômiale quand le mineur interdit est la réunion disjointe de plusieurs longs circuits ou un prisme.