1 Search Results for "Idleman, Mark"

Document

DOI: 10.4230/OASIcs.SOSA.2018.3

Congestion Minimization for Multipath Routing via Multiroute Flows

Authors: Chandra Chekuri and Mark Idleman

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract

Congestion minimization is a well-known routing problem for which there is an O(log n/loglog n)-approximation via randomized rounding due to Raghavan and Thompson. Srinivasan 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 gave a different dependentrounding scheme and derandomization. Doerr et al. 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. One advantage of the simpler rounding is an improved bound on the congestion when the path lengths are short.

Cite as

Chandra Chekuri and Mark Idleman. Congestion Minimization for Multipath Routing via Multiroute Flows. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 3:1-3:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chekuri_et_al:OASIcs.SOSA.2018.3,
  author =	{Chekuri, Chandra and Idleman, Mark},
  title =	{{Congestion Minimization for Multipath Routing via Multiroute Flows}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{3:1--3:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.3},
  URN =		{urn:nbn:de:0030-drops-82984},
  doi =		{10.4230/OASIcs.SOSA.2018.3},
  annote =	{Keywords: multipath routing, congestion minimization, multiroute flows}
}

Refine by Author
1 Chekuri, Chandra
1 Idleman, Mark

Refine by Classification

Refine by Keyword
1 congestion minimization
1 multipath routing
1 multiroute flows

Refine by Type
1 document

Refine by Publication Year
1 2018

1 Search Results for "Idleman, Mark"

Congestion Minimization for Multipath Routing via Multiroute Flows

Abstract

Cite as

Thanks for your feedback!

Could not send message