License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.39
URN: urn:nbn:de:0030-drops-115351
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11535/
Go to the corresponding LIPIcs Volume Portal

Nguyen Kim, Thang

A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing

pdf-format:
LIPIcs-ISAAC-2019-39.pdf (0.5 MB)

Abstract

We consider the virtual circuit routing problem in the stochastic model with uniformly random arrival requests. In the problem, a graph is given and requests arrive in a uniform random order. Each request is specified by its connectivity demand and the load of a request on an edge is a random variable with known distribution. The objective is to satisfy the connectivity request demands while maintaining the expected congestion (the maximum edge load) of the underlying network as small as possible.
Despite a large literature on congestion minimization in the deterministic model, not much is known in the stochastic model even in the offline setting. In this paper, we present an O(log n/log log n)-competitive algorithm when optimal routing is sufficiently congested. This ratio matches to the lower bound Omega(log n/ log log n) (assuming some reasonable complexity assumption) in the offline setting. Additionally, we show that, restricting on the offline setting with deterministic loads, our algorithm yields the tight approximation ratio of Theta(log n/log log n). The algorithm is essentially greedy (without solving LP/rounding) and the simplicity makes it practically appealing.

BibTeX - Entry

@InProceedings{nguyenkim:LIPIcs:2019:11535,
  author =	{Thang Nguyen Kim},
  title =	{{A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{39:1--39:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11535},
  URN =		{urn:nbn:de:0030-drops-115351},
  doi =		{10.4230/LIPIcs.ISAAC.2019.39},
  annote =	{Keywords: Approximation Algorithms, Congestion Minimization}
}

Keywords: Approximation Algorithms, Congestion Minimization
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI