2026-08-05T12:20:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18157 2024-03-06T11:01:10Z ddc:004 open_access

Frameworks for Nonclairvoyant Network Design with Deadlines or Delay Touitou, Noam Online Deadlines Delay Network Design Nonclairvoyant 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Noam Touitou 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.105 urn:nbn:de:0030-drops-181578 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.105 eng https://creativecommons.org/licenses/by/4.0/legalcode