Actualités du LIPN

Le séminaire OCAD recevra le 6 avril Damien Regnault (ATER au LIF-CMI, Marseille).

Cet exposé commence par la présentation rapide de la règle Minorité stochastique et de ses particularités. Ensuite, je présenterai une application de cette règle pour modéliser la formation de quasi-cristaux.

Considérons un graphe où chaque sommet reçoit la couleur noire ou blanche. Une arête contient une erreur si elle relie deux sommets de la même couleur. Minorité est une dynamique stochastique minimisant rapidement l’énergie. Sous cette dynamique, un sommet, chosi aléatoirement et uniformément parmi l’ensemble des sommets, peut changer d’état si au moins la moitié des arêtes qui lui sont adjacentes sont erronées.. Cette dynamique est sensible à la topologie du graphe et son analyse fine s’est révélée compliquée.

En physique, dans les années 70, il était conjecturé que toutes les structures ordonnées soient périodiques. En 1984, un contre-matériaux fût découvert et reçu le nom de quasi-cristal. Dès 1974, Penrose avait présenté un structure théorique ordonnée et apériodique. Le but de notre projet est de présenter un modèle pour expliquer la formation d’une telle structure. Pour cela, nous considérons le modèle des pavages par coupe et projection (qui contient le pavage de Penrose). En définissant une notion d’erreur et d’énergie sur ces pavages, la règle Minorité procédant par flips permet de converger rapidement expérimentalement vers une structure ordonnée qui selon la famille de pavages par coupe et projection considérée est soit périodique, soit apériodique. Je présenterai nos résultats expérimentaux ainsi que notre analyse de cette dynamique pour les pavages 2 vers 1 (mots sur deux lettres).

L’équipe OCAD accueille Rosiane de Freitas Rodrigues (D.Sc. DCC/ICE - Federal University of Amazonas COPPE-Federal University of Rio de Janeiro, Brazil ).

This work deals with scheduling problems with unit execution time jobs, time-windows constraints, parallel machines and the objective function of minimizing the total number of tardy jobs. The emphasis is on deterministic scheduling, characterization theorems, polynomial time algorithms and their computational complexities, and the use of graph theoretical tools, whenever is possible. New models and characterizations have been proposed, that result in better algorithms. For the problems 1 | pj=1; rj | sum Uj, and P | pj=1; rj | sum Uj, formulated in the 3-field notation, a time complexity of O(n log n) was obtained. For the problems 1 | pj=1; rj | sum wjUj, and P | pj=1; rj | sum wjUj , a better upper bound with O(n² (1+logm/m) ) time complexity was obtained. The best time complexity for such problems was O(n^3m), based on network flows techniques.

We also consider a multi-purpose machine scheduling problem, where jobs should be executed in some machine belonging to a given subset of the set of machines. The problem is PMPM | pj=1; rj | sum wjUj, with n independent unit-time jobs, time window constraints, m identical parallel multi-purpose machines, and the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n²m(n + log m)), employing network flow techniques. We develop an algorithm that uses basic concepts of computer science to handle more efficiently successive nesting of on-time jobs, with O(n³) overall time complexity.

It is expected that the results serve as a means for better understanding of other scheduling problems, offering new characterizations and more efficient algorithms.

L’équipe OCAD accueille Nicolas Lermé (doctorant, LIPN).

In few years, graph cuts have become a leading method for solving a wide range of problems in computer vision and graphics. However, graph cuts involve the construction of huge graphs which sometimes do not fit in memory.

Currently, most of the max-flow algorithms are totally impracticable to solve such large scale problems. In the image segmentation context, some authors have proposed banded of hierarchical approximation methods to get round this problem.

We propose a new strategy for reducing graphs during the creation of the graph where the nodes of the reduced graph are typically located in a narrow band surrounding the object edges.

Empirically, solutions obtained on the reduced graphs are identical to the solutions on the complete graphs. Moreover, the time required by the reduction if often compensated by the time that would be needed to create the remove nodes and the additional time required by the max-flow on the larger graph. Finally, we show experiments for segmenting large volume data in 2D and 3D.

L’équipe OCAD accueille François Delbot (docteur, IBISC, Université d’Évry).

La théorie de la complexité distingue les problèmes que l’on sait résoudre en un temps polynomial en la taille des données (que l’on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l’état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l’on peut qualifier de déraisonnable).

C’est pour cette raison que la communauté scientifique s’est tournée vers les algorithmes (polynomiaux) d’approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d’approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d’approximation de k si la taille de toute solution pouvant être retournée par l’algorithme est inférieure ou égale à k fois la taille de la solution optimale).

Dans la littérature, on en vient à considérer qu’un algorithme est plus performant qu’un autre lorsqu’il possède un plus petit rapport d’approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d’un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution).

Dans les travaux que je vais vous présenter, nous avons tenté de mieux "capturer" le comportement des algorithmes d’approximation en allant plus loin que le simple rapport d’approximation en pire cas (en nous focalisant sur le problème du Vertex Cover) :

En montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l’algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l’optimum lorsque n tend vers l’infini.

En évaluant les performances moyennes d’un algorithme. Nous avons prouvé que l’algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d’approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n’importe quel graphe. Ce résultat, combiné à d’autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d’approximation en pire cas .

En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu’il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande).

Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies.

On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d’approximation (fonction du degré max. du graphe).

Tous ces résultats montrent que le rapport d’approximation en pire cas n’est pas toujours suffisant pour caractériser l’intégralité de la qualité d’un algorithme et que d’autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour.