A Combinatorial Approximation Algorithm for the Multicommodity Flow Problem

David Coudert 1 Hervé Rivano 1 Xavier Roche 2
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
Abstract : This work is motivated by the need for approximation algorithms for the integral multicommodity flow problem which arise in numerous optimization scenarios, including the design of telecommunication networks. We improve on one of the most efficient known combinatorial approximation algorithm for fractional multicommodity flow by using an incremental approach. This approach is validated by experimental results, which show a significant speed-up.
Type de document :
Communication dans un congrès
International Workshop on Approximation and Online Algorithms (WAOA'03), 2003, Budapest, Hungary. Springer, 2909, pp.193-230, 2003, Lecture Notes in Computer Science. 〈10.1007/b95598〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00429176
Contributeur : David Coudert <>
Soumis le : dimanche 1 novembre 2009 - 15:11:10
Dernière modification le : lundi 5 novembre 2018 - 15:36:03
Document(s) archivé(s) le : jeudi 17 juin 2010 - 18:55:16

Fichier

CRR-WAOA03.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

David Coudert, Hervé Rivano, Xavier Roche. A Combinatorial Approximation Algorithm for the Multicommodity Flow Problem. International Workshop on Approximation and Online Algorithms (WAOA'03), 2003, Budapest, Hungary. Springer, 2909, pp.193-230, 2003, Lecture Notes in Computer Science. 〈10.1007/b95598〉. 〈inria-00429176〉

Partager

Métriques

Consultations de la notice

286

Téléchargements de fichiers

99