Hardness of Approximating the Traffic Grooming Problem

Omid Amini (1) , Stéphane Pérennes (1) , Ignasi Sau (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

Le groupage est un problème central dans l'étude des réseaux optiques. Dans cet article, on propose le premier résultat d'inapproximabilité pour le problème du groupage, en affirmant la conjecture de Chow et Lin (2004, Networks, 44, 194-202), selon laquelle le groupage est APX-complet. On étudie aussi une version amortie du problème de sous-graphe le plus dense dans un graphe donné: trouver le sous-graphe de taille minimum ayant le degré minimum au moins d, d>=3. On démontre que ce dernier n'a pas d'approximation à un facteur constant.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux et télécommunications [cs.NI]

Omid Amini, Stéphane Pérennes, Ignasi Sau. Hardness of Approximating the Traffic Grooming Problem. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.45-48. ⟨inria-00176960⟩