Online Algorithms with Randomly Infused Advice

[2302.05366] Online Algorithms with Randomly Infused Advice Skip to main content Search Submit Donate Log in Search arXiv Press Enter to search · Advanced search Computer Science > Data Structures and Algorithms arXiv:2302.05366 (cs) [Submitted on 10 Feb 2023 ( v1 ), last revised 15 Apr 2026 (this version, v5)] Title: Online Algorithms with Randomly Infused Advice Authors: Yuval Emek , Yuval Gil , Maciej Pacut , Stefan Schmid View a PDF of the paper titled Online Algorithms with Randomly Infused Advice, by Yuval Emek and 3 other authors View PDF HTML (experimental) Abstract: We introduce a novel method for the rigorous quantitative evaluation of online algorithms that relaxes the "radical worst-case" perspective of classic competitive analysis. In contrast to prior work, our method, referred to as randomly infused advice (RIA), does not make any probabilistic assumptions about the input sequence and does not rely on the development of designated online algorithms. Rather, it can be applied to existing online randomized algorithms, introducing a means to evaluate their performance in scenarios that lie outside the radical worst-case regime. More concretely, an online algorithm ALG with RIA benefits from pieces of advice generated by an omniscient but not entirely reliable oracle. The crux of the new method is that the advice is provided to ALG by writing it into the buffer B from which ALG normally reads its random bits, hence allowing us to augment it through a very simple and non-intrusive interface. The (un)reliability of the oracle is captured via a parameter 0 {\le} {\alpha} {\le} 1 that determines the probability (per round) that the advice is successfully infused by the oracle; if the advice is not infused, which occurs with probability 1 - {\alpha}, then the buffer B contains fresh random bits (as in the classic online setting). The applicability of the new RIA method is demonstrated by applying it to three extensively studied online problems: paging, uniform metrical task systems, and online set cover. For these problems, we establish new upper bounds on the competitive ratio of classic online algorithms that improve as the infusion parameter {\alpha} increases. These are complemented with (often tight) lower bounds on the competitive ratio of online algorithms with RIA for the three problems. Comments: Appeared at ESA 2023. This version includes an elaborated discussion on online algorithms that access past coin tosses Subjects: Data Structures and Algorithms (cs.DS) Cite as: arXiv:2302.05366 [cs.DS] (or arXiv:2302.05366v5 [cs.DS] for this version) https://doi.org/10.48550/arXiv.2302.05366 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Yuval Emek [ view email ] [v1] Fri, 10 Feb 2023 16:42:27 UTC (145 KB) [v2] Mon, 13 Feb 2023 07:24:12 UTC (145 KB) [v3] Fri, 12 May 2023 09:11:32 UTC (146 KB) [v4] Sat, 5 Aug 2023 16:34:53 UTC (147 KB) [v5] Wed, 15 Apr 2026 11:54:47 UTC (127 KB) Full-text links: Access Paper: View a PDF of the paper titled Online Algorithms with Randomly Infused Advice, by Yuval Emek and 3 other authors View PDF HTML (experimental) TeX Source view license Current browse context: cs.DS < prev | next > new | recent | 2023-02 Change to browse by: cs References & Citations NASA ADS Google Scholar Semantic Scholar export BibTeX citation Loading... BibTeX formatted citation × loading... Data provided by: Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer ( What is the Explorer? ) Connected Papers Toggle Connected Papers ( What is Connected Papers? ) Litmaps Toggle Litmaps ( What is Litmaps? ) scite.ai Toggle scite Smart Citations ( What are Smart Citations? ) Code, Data, Media Code, Data and Media Associated with this Article alphaXiv Toggle alphaXiv ( What is alphaXiv? ) Links to Code Toggle CatalyzeX Code Finder for Papers ( What is CatalyzeX? ) DagsHub Toggle DagsHub ( What is DagsHub? ) GotitPub Toggle Gotit.pub ( What is GotitPub? ) Huggingface Toggle Hugging Face ( What is Huggingface? ) ScienceCast Toggle ScienceCast ( What is ScienceCast? ) Demos Demos Replicate Toggle Replicate ( What is Replicate? ) Spaces Toggle Hugging Face Spaces ( What is Spaces? ) Spaces Toggle TXYZ.AI ( What is TXYZ.AI? ) Related Papers Recommenders and Search Tools Link to Influence Flower Influence Flower ( What are Influence Flowers? ) Core recommender toggle CORE Recommender ( What is CORE? ) Author Venue Institution Topic About arXivLabs arXivLabs: experimental projects with community collaborators arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website. Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them. Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs . Which authors of this paper are endorsers? | Disable MathJax ( What is MathJax? ) We gratefully acknowledge support from our major funders , member institutions , , and all contributors. About · Help · Contact · Subscribe · Copyright · Privacy · Accessibility · Operational Status (opens in new tab) Major funding support from

Related documents

• Online Safety (Recommender Algorithms) Bill 2026#186353
• Preserving Platform Innovation with a Narrow Exception: Section 230(c)(1) Immunity for Algorithmic Recommendations#651349
• The Matroid Secretary Conjecture is True#1084500
• Distributed Artificial Intelligence: An Annotated Bibliography#490928
• Modeling Random Systems#1179845