License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2023.105
URN: urn:nbn:de:0030-drops-181578
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18157/
Go to the corresponding LIPIcs Volume Portal

Touitou, Noam

Frameworks for Nonclairvoyant Network Design with Deadlines or Delay

pdf-format:
LIPIcs-ICALP-2023-105.pdf (0.8 MB)

Abstract

Clairvoyant network design with deadlines or delay has been studied extensively, culminating in an O(log n)-competitive general framework, where n is the number of possible request types (Azar and Touitou, FOCS 2020). In the nonclairvoyant setting, the problem becomes much harder, as Ω(√n) lower bounds are known for certain problems (Azar et al., STOC 2017). However, no frameworks are known for the nonclairvoyant setting, and previous work focuses only on specific problems, e.g., multilevel aggregation (Le et al., SODA 2023).
In this paper, we present the first nonclairvoyant frameworks for network design with deadlines or delay. These frameworks are nearly optimal: their competitive ratio is Õ(√n), which matches known lower bounds up to logarithmic factors.

BibTeX - Entry

@InProceedings{touitou:LIPIcs.ICALP.2023.105,
  author =	{Touitou, Noam},
  title =	{{Frameworks for Nonclairvoyant Network Design with Deadlines or Delay}},
  booktitle =	{50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
  pages =	{105:1--105:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-278-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{261},
  editor =	{Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18157},
  URN =		{urn:nbn:de:0030-drops-181578},
  doi =		{10.4230/LIPIcs.ICALP.2023.105},
  annote =	{Keywords: Online, Deadlines, Delay, Network Design, Nonclairvoyant}
}

Keywords: Online, Deadlines, Delay, Network Design, Nonclairvoyant
Collection: 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Issue Date: 2023
Date of publication: 05.07.2023

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