Nicolas Catusse logo fr logo en
Docteur en Informatique - Équipe Combinatoire et Recherche Opérationnelle du LIF UMR CNRS 6166.
ATER - Département Informatique de Luminy, Faculté des Science de Luminy, Aix-Marseille Université.

Recherche

Intérêts : Algorithmique des graphes et réseaux. Algorithme d'approximation. Géométrie algorithmique. Distance. Optimisation combinatoire.

Thèse de Doctorat en Informatique


Mots-clés : géométrie algorithmique, algorithme d'approximation, distance, plan normé, plongement isométrique, conception de réseau.

Soutenue publiquement le 9 décembre 2011 à Marseille.

Titre : Spanners pour des réseaux géométriques et plongements dans le plan.

Jury :


Résumé : Dans cette thèse, nous nous intéressons à plusieurs problèmes liés à la conception de réseaux géométriques et aux plongements isométriques dans le plan. Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinèaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux. Nous nous intéressons ensuite à la recherche d'un spanner (un sous-graphe approximant les distances) planaire pour les graphes de disques unitaires (UDG) qui modélise les réseaux ad hoc sans fils. Nous présentons un algorithme qui construit un spanner planaire avec un facteur d'étirement constant en terme de distance de graphe pour UDG. Cet algorithme utilise uniquement des propriétés locales et peut donc être implémenté de manière distribuée. Finalement nous étudions le problème de la reconnaissance des espaces plongeables isométriquement dans le plan l_1 pour lequel nous proposons un algorithme en temps optimal O(n^2) pour sa résolution, ainsi que la généralisation de ce problème aux plans normés dont la boule unitaire est un polygone convexe central symétrique.

La document de thèse : these_Catusse.pdf

Les transparents de soutenance : soutenance_Catusse.pdf

Challenge ROADEF/EURO 2012

Qualifié pour la phase finale, 10ème équipe sur 82 - Problème de réaffectation de processus sur un ensemble de machines (page du challenge).

Revues internationales

N. Catusse, V. Chepoi et Y. Vaxès.
Embedding into the rectilinear plane in optimal O(n^2) time, Theoretical Computer Science 412 (2011), 2425-2433 (arXiv e-print).

N. Catusse, V. Chepoi, K. Nouioua et Y. Vaxès (2010).
Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm, Algorithmica 63 (2012), 551-567 (arXiv e-print).

N. Catusse, V. Chepoi, K. Nouioua et Y. Vaxès (2011).
Bidirectional Minimum Manhattan network problem (soumis, arXiv e-print).

Conférences internationales

N. Catusse, V. Chepoi et Y. Vaxès.
Planar Hop Spanners for Unit Disk Graphs.
6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Movile Entities (AlgoSensors'10).

N. Catusse, V. Chepoi et Y. Vaxès.
Planar Hop Spanners for Unit Disk Graphs.
26th European Workshop on Computational Geometry (EuroCG'10).

N. Catusse, V. Chepoi et Y. Vaxès.
Embedding into the rectilinear plane in optimal O(n^2) time.
26th European Workshop on Computational Geometry (EuroCG'10).

Conférences nationales

N. Catusse, V. Chepoi, K. Nouioua et Y. Vaxès.
Algorithme d'approximation facteur 2 pour les réseaux de Manhattan orientés minimaux.
Journées Graphe et Algorithme 2011.

N. Catusse, V. Chepoi et Y. Vaxès.
Hop Spanner Planaire pour Unit Disk Graphe.
Journées automnales ResCom 2010.

N. Catusse, V. Chepoi, K. Nouioua et Y. Vaxès.
Algorithme d'approximation facteur 2.5 pour le problème du réseau B-Manhattan minimal.
Journées Graphe et Algorithme 2010.

N. Catusse, V. Chepoi et Y. Vaxès.
Plongement dans le plan rectilinéaire en temps optimal O(n^2) (résumé, slides).
Journées Géométrie Algorithmique 2010.

N. Catusse, V. Chepoi et Y. Vaxès.
Plongement dans le plan rectilinéaire en temps optimal O(n^2) (slides).
Journées Graphe et Algorithme 2009.

Enseignements

2011-2012 L3 informatique. Système d'exploitation
L3 informatique. Réseau et Communication
L2 informatique. Projet Informatique 2012
2010-2011 L3 informatique. Système d'exploitation
L1 informatique. Initiation à l'informatique
2009-2010 Licence. Préparation au C2i
L3 informatique. Programmation Objet
2008-2009 L2 informatique. Projet Informatique 2009
L1 informatique. Initiation à l'informatique
2007-2008 Tutorat Informatique.

Cursus

2008-2011 Doctorat en Informatique à l'Université de la Méditerranée (Allocataire-Moniteur)
Directeurs de thèse : Victor Chepoi et Yann Vaxès
Mention Très honorable
2007-2008 Master 2 d'Informatique Fondamentale à l'Université de la Méditerranée - Filière Structures Discrètes et Recherche Opérationnelle
Mémoire intitulé "Spanners Planaires pour Unit Disk Graph"
Encadrants : Victor Chepoi et Yann Vaxès
Mention Très Bien
2006-2007 Master 1 d'Informatique à la Faculté des Sciences de Luminy - Université de la Méditerranée
Mention Très Bien
2004-2006 Licence d'Informatique à la Faculté des Sciences de Luminy - Université de la Méditerranée
Mention Très Bien
2003-2004 Baccalauréat Scientifique au Lycée de Lorgues - Option Science de l'ingénieur
Mention Bien

Coordonnées

LIF - UFR Sciences Luminy,
163 avenue de Luminy,
13288 Marseille Cedex 9, France.

Bureau 611 (TPR1, Entrée G, 6ème étage)
Tél. (+33) 4 91 82 93 58
Fax. (+33) 4 91 82 92 75
Mél. Nicolas.Catusse[at]lif.univ-mrs.fr