Problème de partitionnement pour la localisation du trafic.

Public concerné : DEA Informatique, DEA RSD, DEA MDFI
Description du sujet :
La conception moderne des réseaux de télécommunication a été bouleversée par l´introduction de la fibre optique à très grande capacité. Il devient aujourd´hui beaucoup moins coûteux de passer d´une capacité simple à une capacité quadruple. En particulier, les échelles de prix ressemblent davantage maintenant à un facteur logarithmique qu´à un facteur linéaire. Dans ce contexte, un opérateur cherchera naturellement à regrouper le trafic au maximum sur des boucles plus proches des utilisateurs finaux (on évite le terme ``boucle locale´´ qui a été dévoyé depuis, mais le sens premier du terme y correspond).
Objectifs :
On modélise donc la demande comme étant un certain nombre de couples de points du plan avec un certain débit. Etant donné un ensemble de demandes et donc de points, on cherche à partitionner les points du plan, de sorte que chaque partition corresponde à la boucle d´une fibre. Le coût associé à une fibre évoluera typiquement logarithmiquement avec la capacité, et linéairement avec la longueur du plus court chemin du voyageur de commerce entre les points de la partition. D´autres formes de coût pourront être envisagées.
Connaissances prérequises : Goût pour l´algorithmique.
Matériel mis à disposition : Le projet MASCOTTE dispose de l´ensemble du support INRIA

INRIA - Projet MASCOTTE
2004, route des Lucioles
B.P. 93 F-06902 Sophia Antipolis  Cedex