Document Open Access Logo

A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing

Author Thắng Nguyễn Kim

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2019.39.pdf
  • Filesize: 466 kB
  • 12 pages

Document Identifiers

Author Details

Thắng Nguyễn Kim
  • IBISC, Univ Evry, University Paris Saclay, Evry, France

Funding

Research supported by the ANR project OATA no ANR-15-CE40-0015-01.

Cite AsGet BibTex

Thắng Nguyễn Kim. A Competitive Algorithm for Random-Order Stochastic Virtual Circuit Routing. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 39:1-39:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ISAAC.2019.39

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Approximation Algorithms
  • Congestion Minimization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Shipra Agrawal and Nikhil R Devanur. Fast algorithms for online stochastic convex programming. In Proc. 26th ACM-SIAM symposium on Discrete algorithms, pages 1405-1424, 2014. Google Scholar
  2. Matthew Andrews and Lisa Zhang. Logarithmic hardness of the directed congestion minimization problem. In Proc. 38th Symposium on Theory of Computing, pages 517-526, 2006. Google Scholar
  3. James Aspnes, Yossi Azar, Amos Fiat, Serge Plotkin, and Orli Waarts. On-line routing of virtual circuits with applications to load balancing and machine scheduling. Journal of the ACM (JACM), 44(3):486-504, 1997. Google Scholar
  4. Baruch Awerbuch, Yossi Azar, Edward F Grove, Ming-Yang Kao, P Krishnan, and Jeffrey Scott Vitter. Load balancing in the 𝓁_p-norm. In Proc. 36th Foundations of Computer Science, pages 383-391, 1995. Google Scholar
  5. Ioannis Caragiannis. Better bounds for online load balancing on unrelated machines. In Proc. 19th Symposium on Discrete Algorithms, pages 972-981, 2008. Google Scholar
  6. Chandra Chekuri and Mark Idleman. Congestion minimization for multipath routing via multiroute flows. In Proc. 1st Symposium on Simplicity in Algorithms, 2018. Google Scholar
  7. Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, pages 575-584, 2010. Google Scholar
  8. Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, and Kunal Talwar. Hardness of routing with congestion in directed graphs. In Proc. 39th ACM Symposium on Theory of Computing, pages 165-178, 2007. Google Scholar
  9. Benjamin Doerr. Randomly rounding rationals with cardinality constraints and derandomizations. In Symposium on Theoretical Aspects of Computer Science, pages 441-452, 2007. Google Scholar
  10. Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, and Aravind Srinivasan. Dependent rounding and its applications to approximation algorithms. Journal of the ACM, 53(3):324-360, 2006. Google Scholar
  11. Ashish Goel and Piotr Indyk. Stochastic load balancing and related problems. In Proc. 40th Symposium on Foundations of Computer Science, pages 579-586, 1999. Google Scholar
  12. Anupam Gupta, Amit Kumar, Viswanath Nagarajan, and Xiangkun Shen. Stochastic load balancing on unrelated machines. In Proc. 29th Symposium on Discrete Algorithms, pages 1274-1285, 2018. Google Scholar
  13. Anupam Gupta and Marco Molinaro. How the experts algorithm can help solve LPs online. Mathematics of Operations Research, 41(4):1404-1431, 2016. Google Scholar
  14. Varun Gupta, Benjamin Moseley, Marc Uetz, and Qiaomin Xie. Stochastic online scheduling on unrelated machines. In Conference on Integer Programming and Combinatorial Optimization, pages 228-240, 2017. Google Scholar
  15. Sungjin Im, Benjamin Moseley, and Kirk Pruhs. Stochastic scheduling of heavy-tailed jobs. In Proc. 32nd Symposium on Theoretical Aspects of Computer Science, pages 474-486, 2015. Google Scholar
  16. Wataru Kishimoto and Masashi Takeuchi. m-route flows in a network. Electronics and Communications in Japan (Part III: Fundamental Electronic Science), 77(5):1-18, 1994. Google Scholar
  17. Jon Kleinberg, Yuval Rabani, and Éva Tardos. Allocating bandwidth for bursty connections. SIAM Journal on Computing, 30(1):191-217, 2000. Google Scholar
  18. Jian Li and Amol Deshpande. Maximizing expected utility for stochastic combinatorial optimization problems. Mathematics of Operations Research, 2018. Google Scholar
  19. Jian Li and Wen Yuan. Stochastic combinatorial optimization via poisson approximation. In Proc. 45th Symposium on Theory of Computing, pages 971-980, 2013. Google Scholar
  20. Nicole Megow, Marc Uetz, and Tjark Vredeveld. Models and algorithms for stochastic online scheduling. Mathematics of Operations Research, 31(3):513-525, 2006. Google Scholar
  21. Rolf H Möhring, Andreas S Schulz, and Marc Uetz. Approximation in stochastic scheduling: the power of LP-based priority policies. Journal of the ACM, 46(6):924-942, 1999. Google Scholar
  22. Marco Molinaro. Online and random-order load balancing simultaneously. In Proc. 28th ACM-SIAM Symposium on Discrete Algorithms, pages 1638-1650, 2017. Google Scholar
  23. Prabhakar Raghavan and Clark D Thompson. Randomized rounding: a technique for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365-374, 1987. Google Scholar
  24. Aravind Srinivasan. Distributions on level-sets with applications to approximation algorithms. In Proc. 42nd IEEE Symposium on Foundations of Computer Science, pages 588-597, 2001. Google Scholar
  25. Nguyen Kim Thang. Online primal-dual algorithms with configuration linear programs. arXiv, 2017. URL: http://arxiv.org/abs/1708.04903.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact