1 Search Results for "Leguay, Jérémie"

Document
DOI: 10.4230/LIPIcs.STACS.2022.6
Approximability of Robust Network Design: The Directed Case

Authors: Yacine Al-Najjar, Walid Ben-Ameur, and Jérémie Leguay

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We consider robust network design problems where an uncertain traffic vector belonging to a polytope has to be dynamically routed to minimize either the network congestion or some linear reservation cost. We focus on the variant in which the underlying graph is directed. We prove that an O(√k) = O(n)-approximation can be obtained by solving the problem under static routing, where k is the number of commodities and n is the number of nodes. This improves previous results of Hajiaghayi et al. [SODA'2005] and matches the Ω(n) lower bound of Ene et al. [STOC'2016] and the Ω(√k) lower bound of Azar et al. [STOC'2003]. Finally, we introduce a slightly more general problem version where some flow restrictions can be added. We show that it cannot be approximated within a ratio of k^{c/(log log k)} (resp. n^{c/(log log n)}) for some constant c. Making use of a weaker complexity assumption, we prove that there is no approximation within a factor of 2^{log^{1- ε} k} (resp. 2^{log^{1- ε} n}) for any ε > 0.
Cite as

Yacine Al-Najjar, Walid Ben-Ameur, and Jérémie Leguay. Approximability of Robust Network Design: The Directed Case. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{alnajjar_et_al:LIPIcs.STACS.2022.6,
  author =	{Al-Najjar, Yacine and Ben-Ameur, Walid and Leguay, J\'{e}r\'{e}mie},
  title =	{{Approximability of Robust Network Design: The Directed Case}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.6},
  URN =		{urn:nbn:de:0030-drops-158165},
  doi =		{10.4230/LIPIcs.STACS.2022.6},
  annote =	{Keywords: Robust Optimization, Network Design, Approximation, Inapproximability, Competitive Ratio of Oblivious Routing}
}
  • Refine by Author
  • 1 Al-Najjar, Yacine
  • 1 Ben-Ameur, Walid
  • 1 Leguay, Jérémie

  • Refine by Classification
  • 1 Theory of computation
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Routing and network design problems

  • Refine by Keyword
  • 1 Approximation
  • 1 Competitive Ratio of Oblivious Routing
  • 1 Inapproximability
  • 1 Network Design
  • 1 Robust Optimization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

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