Congestion minimization for multipath routing via multiroute flows

Chandra Chekuri, Mark Idleman

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Congestion minimization is a well-known routing problem for which there is an O(log n/log log n)-approximation via randomized rounding [17]. Srinivasan [18] formally introduced the low-congestion multi-path routing problem as a generalization of the (single-path) congestion minimization problem. The goal is to route multiple disjoint paths for each pair, for the sake of fault tolerance. Srinivasan developed a dependent randomized scheme for a special case of the multi-path problem when the input consists of a given set of disjoint paths for each pair and the goal is to select a given subset of them. Subsequently Doerr [7] gave a different dependent rounding scheme and derandomization. In [8] the authors considered the problem where the paths have to be chosen, and applied the dependent rounding technique and evaluated it experimentally. However, their algorithm does not maintain the required disjointness property without which the problem easily reduces to the standard congestion minimization problem. In this note we show a simple algorithm that solves the problem correctly without the need for dependent rounding - standard independent rounding suffices. This is made possible via the notion of multiroute flows originally suggested by Kishimoto et al. [13]. One advantage of the simpler rounding is an improved bound on the congestion when the path lengths are short.

Original languageEnglish (US)
Title of host publication1st Symposium on Simplicity in Algorithms, SOSA 2018 - Co-located with the 29th ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
EditorsRaimund Seidel
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770644
StatePublished - Jan 1 2018
Event1st Symposium on Simplicity in Algorithms, SOSA 2018 - New Orleans, United States
Duration: Jan 7 2018Jan 10 2018

Publication series

NameOpenAccess Series in Informatics
ISSN (Print)2190-6807


Other1st Symposium on Simplicity in Algorithms, SOSA 2018
Country/TerritoryUnited States
CityNew Orleans


  • Congestion minimization
  • Multipath routing
  • Multiroute flows

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modeling and Simulation


Dive into the research topics of 'Congestion minimization for multipath routing via multiroute flows'. Together they form a unique fingerprint.

Cite this