Skip to Main content Skip to Navigation
Conference papers

Hardness of Approximating the Traffic Grooming Problem

Omid Amini 1 Stéphane Pérennes 1 Ignasi Sau Valls 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176960
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 1:43:59 AM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Thursday, September 27, 2012 - 12:57:02 PM

File

59-APS-Algotel.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00176960, version 1

Collections

Citation

Omid Amini, Stéphane Pérennes, Ignasi Sau Valls. 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⟩

Share

Metrics

Record views

635

Files downloads

140