Hardness of Approximating the Traffic Grooming Problem

Description

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.

Abstract

National audience

Additional details