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.
Complete list of metadatas

https://hal.inria.fr/inria-00429176
Contributor : David Coudert <>
Submitted on : Sunday, November 1, 2009 - 3:11:10 PM
Last modification on : Monday, September 9, 2019 - 1:42:09 PM
Long-term archiving on : Thursday, June 17, 2010 - 6:55:16 PM

File

CRR-WAOA03.pdf
Files produced by the author(s)

Identifiers

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. pp.193-230, ⟨10.1007/b95598⟩. ⟨inria-00429176⟩

Share

Metrics

Record views

324

Files downloads

196