Skip to Main content Skip to Navigation
New interface
Conference papers

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 metadata
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Sunday, November 1, 2009 - 3:11:10 PM
Last modification on : Thursday, August 4, 2022 - 4:52:39 PM
Long-term archiving on: : Thursday, June 17, 2010 - 6:55:16 PM


Files produced by the author(s)




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⟩



Record views


Files downloads