Mini-Projet: Javanco

Description	Javanco est un logiciel permettant de faire des manipulations sur les graphes. Il est développé par le T-COM, un laboratoire de la faculté I&C de l'EPFL. Le but de ce projet est d'implémenter des algorithmes simples et connus de la théorie des graphes à l'aide de Javanco.
Disponibilité	Printemps 2008
Environnement	Programmation
Responsable	Benjamin Leroy-Beaulieu

Mini-Projet: Etude de la coloration online dans les Split-Graphs

Description	Le but de se projet est de se familiariser avec la coloration dans les graphes et en particulier avec la coloration online. L'étudiant s'intéressera à ce problème dans la classe de graphes particulière que sont les split-graphs et tâchera de trouver des bornes à l'application d'un algorithme trivial dans cette classe.
Disponibilité	Printemps 2008
Environnement	Papier, crayon.
Responsable	Benjamin Leroy-Beaulieu

Sur le problème du Sac-à-dos 0-1.

Description	Le problème du sac-à-dos binaire avec une variable continue unique (KPC) est une extension naturelle du problème du sac-à-dos binaire classique (KP). Il s'agit ici d'étudier des réductions du problème KPC au problème KP.
Keywords	Sac-à-dos binaire
Références	M. Büther, D. Briskorn "Reducing the 0-1 Knapsack Problem with a Single Continuous Variable to the standard 0-1 Knapsack Problem" Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel, No 629, September 2007.
Disponibilité	Hiver 2007-2008.
Environnement	Papier et Crayon.
Responsable	Dominique de Werra

Etude de la déficience dans les cactus

Description	Dans un graphe, une coloration d'arête avec des nombres entiers est consécutive (ou d'intervalles) si pour chaque sommet, les couleurs qui lui sont incidentes sont distinctes et forment un intervalle d'entiers. Ce problème trouve des applications immédiates lors de la confection d'horaire, quand on cherche une solution optimale sans temps d'attente entre certaines tâches. Le concept assez récent de déficience d'un graphe se définit comme la distance minimum qui sépare un graphe donné d'un autre qui lui serait consécutivement colorable. On souhaite ici étudier cette notion dans les cactus, une classe de graphe particulière.
Keywords	Coloration d'arêtes consécutive, déficience, cactus
Références	1. K.Giaro, M.Kubale et M.Malafiejski, "Consecutive colorings of the edges of general graphs", Discrete Mathematics, 236, pg 131-143. 2. S.Emery, "Classes de graphes avec déficience reconnaissable en temps polynomial", projet de master, hiver 06-07.
Disponibilité	Hiver 2007-2008.
Environnement	Papier et Crayon.
Responsable	Sivan Altinakar

Ordonnancement avec multiprocesseurs

Description	On considère le problème d'atelier ouvert (open shop) où pour certaines opérations on doit regrouper plusieurs processeurs . Il s'agira de déterminer des ordonnancements de durée minimum en tenant compte des multiprocesseurs. On pourra se baser sur l'article de T.Kis, W.Kubiak et D. de W. "Preemptive open shop scheduling with multiprocessors" (à paraître dans Journal of Scheduling) où des hypothèses simplificatrices sont faites. On envisagera ensuite de relâcher ces hypothèses et on proposera des méthodes de résolution approchées.
Keywords	Ordonnancement, Atelier Ouvert
Références	T.Kis, W.Kubiak et D. de Werra "Preemptive open shop scheduling with multiprocessors" (à paraître dans Journal of Scheduling).
Disponibilité	Hiver 2007-2008.
Environnement	Papier et Crayon.
Responsable	Dominique de Werra

Ordonnancement équilibré

Description	Dans le modèle du open shop avec interruptions autorisées où toutes les opérations sont de même durée on résout le problème par une coloration d'arêtes dans un graphe biparti.On supposera en plus dans ce projet que toute opération O(i,j) de la tâche j sur le processeur i a besoin d'un effectif c(i,j) de personnel. On veut partitionner l'ensemble des opérations en  delta lots  (chaque lot est un ensemble d'opérations qui peuvent s'exécuter simultanément (avec le même personnel qui  supervise plusieursopérations à la fois), c.à.d. un couplage dans le graphe biparti associé; delta est le degré maximum du graphe associé) . Pour chaque lot on définit son écart comme la différence entre le plus grand et le plus petit effectif de personnel requis pour les opérations de ce lot. On veut trouver une partition telle que  la somme des écarts des différents lots soit minimum. On peut consulter l'article de S.Martello, W.Pulleyblank, P.Toth, D. de W. :Balanced Optimization problems, O.R. Letters 1984 pour la formulation d'un problème voisin.
Keywords	Ordonnancement, Atelier Ouvert Préemptif, Coloration d'arêtes.
Références	S.Martello, W.Pulleyblank, P.Toth, D. de Werra :Balanced Optimization problems, O.R. Letters 1984
Disponibilité	Hiver 2007-2008.
Environnement	Crayon, Papier
Responsable	Dominique de Werra

GPS et reconnaissance de trajectoire

Description	On demande aux systèmes de navigation (GPS), en plus de leur fonction première de guidage, de fournir des données (position, vitesse du véhicule, géométrie de la route que le véhicule va parcourir, etc.) à des applications d'aide à la conduite. Ces données sont utilisées pour avoir une meilleure représentation de la géométrie de la route ou de détecter des erreurs de digitalisation dans la carte. Pour chaque tronçon parcouru par un véhicule, il faut identifier s'il a déjà été parcouru par un autre véhicule pour faire une moyenne des données correspondant à ce tronçon. Le but du projet consiste à développer et mettre en oeuvre un ou des algorithmes permettant de détecter les tronçons communs d'un ensemble de trajectoires. Comme le nombre de trajectoires de même que leur longueur peuvent être importants, une attention particulière doit être portée sur la rapidité de calcul et la complexité des solutions proposées. Ce projet est proposé en collaboration avec l'entreprise BOSCH.
Keywords	Algorithmique, Complexité.
Références	J. Hershberger, J. Snoeyink "Speeding Up the Douglas-Peucker Line-Simplification Algorithm".
Disponibilité	Hiver 2007-2008. Ce sujet peut donner lieu à deux projets, pour deux étudiants.
Environnement	Programmation
Responsable	Matthieu Plumettaz ou Sivan Altinakar, Michel Mittaz (BOSCH)

Méthodes de résolution pour l'allocation de fréquence dans des réseaux à topologie "mesh"

Description	L'allocation de fréquence est un problème qui a déjà été extensivement étudié dans le cadre des réseaux de téléphones portables. Mais l'émergence de nouveaux concepts de systèmes, tels que les réseaux à topologie "mesh" (réseaux dont tous les hôtes sont connectés de proche en proche sans hiérarchie centrale, formant ainsi une structure en forme de filet) et leur application par exemple au déploiement d'internet dans une ville par la technologie wifi, ont amené à un regain d'intérêt pour ce sujet de recherche. Le projet consiste à implémenter différentes méthodes de résolutions (algorithme tabou, CPLEX), pour ensuite les comparer à des méthodes et résultats théoriques qui existent déjà.
Keywords	Mesh networks, allocation de fréquence, algorithme tabou
Disponibilité	Été 2007 (déjà pris)
Références	1. C. Waber, "Allocations de fréquence dans des réseaux à topologie Mesh", projet de master, hiver 06-07 2. A. Raniwala, K. Gopalan, T. Chiueh, "Centralized channel assignment and routing algorithms for multi-channel wireless mesh networks", Mobile Computing and Comunications Review, volume 8, numéro 2, pages 50-65
Environnement	C++, CPLEX.
Responsable	Sivan Altinakar

Coloration de graphes mixtes

Description	Un graphe mixte est un graphe contenant à la fois des arêtes et des arcs. Nous définissons une coloration des sommets d'un graphe mixte de la manière suivante: chaque sommet reçoit une couleur (càd un entier) telle que deux sommets reliés par une arête aient des couleurs différentes et telle que pour deux sommets x,y reliés par un arc allant de x vers y, la couleur de x soit plus petite ou égale à celle de y. Il s'agit de trouver des bornes pour le nombre chromatique mixte et des classes de graphes mixtes pour lesquelles le problème de la coloration est résoluble en temps polynomiale.
Keywords	Graphes mixtes, coloration, nombre chromatique, complexité.
Disponibilité	Hiver 2007-2008 (déjà pris).
Environnement	Papier, crayon.
Responsable	Bernard Ries