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
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Résumé : 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.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.45-48, 2007
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00176960
Contributeur : David Coudert <>
Soumis le : vendredi 5 octobre 2007 - 01:43:59
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : jeudi 27 septembre 2012 - 12:57:02

Fichier

59-APS-Algotel.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176960, version 1

Collections

Citation

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, 2007. 〈inria-00176960〉

Partager

Métriques

Consultations de la notice

550

Téléchargements de fichiers

112