2026-07-24T12:54:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23378 2025-10-02T12:53:29Z ddc:004 open_access

Online Algorithm Design Beyond the Worst Case (Invited Talk) Gupta, Anupam Beyond Worst-Case Analysis Algorithms with Predictions Random Order Models The analysis of algorithm performance in the worst-case has long been the gold standard of theoretical computer science: it provides a simple, compelling, and robust model, which can often be predictive as well as descriptive. That said, in recent years we have seen an exciting surge in analyzing algorithms using models that go beyond the worst case. Particularly, how can we use ideas from machine learning to inform algorithm design? In this talk we will discuss some of the results and techniques that come out of this endeavor, in both offline and online settings. For example, we will study covering problems like set cover, load balancing problems like scheduling jobs of machines, and cut problems. We will see some of the modeling decisions in beyond worst-case frameworks, as well as the algorithmic ideas - some old, some new - that can be used to give more nuanced guarantees for these classical problems, complementing our understanding of these problem in the worst-case settings. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Gupta 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.1 urn:nbn:de:0030-drops-233786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.1 eng https://creativecommons.org/licenses/by/4.0/legalcode