Dagstuhl Seminar 25471
Online Algorithms beyond Competitive Analysis
( Nov 16 – Nov 21, 2025 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/25471
Organizers
- Sungjin Im (University of California - Santa Cruz, US)
- Nicole Megow (Universität Bremen, DE)
- Debmalya Panigrahi (Duke University - Durham, US)
- Sahil Singla (Georgia Institute of Technology - Atlanta, US)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Shared Documents
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
Schedule
Traditionally, algorithms are studied in a setting where the entire input is known in advance and the goal is to compute an optimal solution with respect to a given objective. In many applications, however, this paradigm is inadequate: inputs arrive over time and decisions must be made as information is revealed. This has given rise to the field of online algorithms, in which input revelation and algorithmic decisions are interleaved, creating a distinctive mix of computational and information constraints. A central theoretical tool for analyzing such algorithms is competitive analysis, which extends worst-case reasoning to the online setting by comparing the performance of an online algorithm to an offline optimum that has full knowledge of the complete input sequence. Over the past decades, this framework has generated a deep and influential body of results, shaped a set of core problems, and established online algorithms as a central area in algorithm design.
At the same time, it has long been recognized that competitive analysis, despite its elegance and conceptual clarity, can be too pessimistic in practice, and can fail to separate algorithms whose empirical performance differs substantially. A canonical illustration is online caching: many deterministic policies share the same worst-case competitive ratio, yet strategies such as least-recently-used can outperform others by large margins on realistic workloads. Motivated by such gaps between worst-case guarantees and observed behavior, the community has increasingly developed and studied beyond-worst-case models for online computation. These approaches aim to preserve rigorous guarantees while incorporating additional structure or flexibility that better reflects practical environments, thereby enabling finer-grained comparisons between algorithms that standard competitive analysis treats as essentially equivalent.
The Dagstuhl Seminar “Online Algorithms beyond Competitive Analysis” (25471) was organized in the context of this broader shift. It brought together researchers working on beyond-worst-case perspectives in online algorithms, to exchange viewpoints across subcommunities, and to identify promising directions and shared challenges. Discussions were structured around three representative themes:
- Online algorithms with predictions (learning-augmented algorithms): models in which an online algorithm is given auxiliary information about the future (e.g., forecasts derived from past data) and is designed to benefit from accurate predictions while remaining robust when predictions are noisy or unreliable.
- Online and dynamic algorithms with recourse: frameworks that relax strict irrevocability by allowing limited revisions to past decisions, capturing settings where changes are possible but costly, and studying how bounded recourse improves achievable guarantees and enables dynamic variants where requirements may both arrive and depart.
- Online stochastic input models: models that assume stochastic structure in arrivals (such as random order or distributional assumptions) to circumvent worst-case barriers, together with emerging efforts to make such models robust to deviations such as outliers or mild correlations.
Organization of the Seminar
The seminar brought together 45 researchers working on online algorithms. The participants embraced both senior and junior researchers, including a number of postdocs and advanced PhD students. During the five days of the seminar, 28 talks of different lengths took place. Six keynote speakers gave an overview of the state-of-the art of the respective area or presented recent highlight results in 60 minutes:
- Christian Coester: A Mirror Descent Approach for Online Algorithms
- Shuchi Chawla: Pandora’s Box
- Jose Correa: Prophet Inequalities
- Anupam Gupta: Online Algorithms with Samples
- Ziv Scully: Survey on Queueing Theoretic Scheduling
- David Wajc: Philosopher inequalities: online Bayesian selection beyond competitive analysis
The remaining slots were filled with shorter talks of 30 minutes and a few 8-minute spotlight talks.
Outcomes
Organizers and participants regard the seminar as a great success. The seminar achieved the goal to bring together researchers from different sub-communities addressing beyond-worst-case analyses, share the state-of-the art research and discuss the current major challenges. The talks were excellent and stimulating; participants connected and actively met in working groups in the afternoon and evenings.
The organizers wish to express their gratitude towards the Scientific Directorate and the administration of the Dagstuhl Center for their great support for this seminar.
Creative Commons BY 4.0
Sungjin Im, Nicole Megow, Debmalya Panigrahi, and Sahil Singla
In many real-world situations, the input to an algorithm is revealed piece-meal over time, and algorithmic decisions must be taken without knowledge of future inputs. This has given rise to the field of online algorithms. Traditionally, the performance of an online algorithm is measured by comparing the quality of the solution produced by the algorithm to that of an offline optimal solution. This framework, called competitive analysis, has led to a beautiful theory of worst-case analysis for online algorithms over the last few decades. At the same time, it has also been painfully obvious that this model is overly pessimistic in many situations and leads to strong lower bounds that bucket together algorithms with significant differences in observed empirical performance. In recent years, there has been an increasing push to go beyond worst-case competitive analysis of online algorithms, and several models and frameworks have been proposed that have attracted much research activity. This Dagstuhl Seminar seeks to bring together the leaders in online algorithms research to discuss and debate these approaches, helping chart the future of online algorithms for the foreseeable future.
We identify three key directions for online algorithms that the seminar will focus on. Each of these directions goes beyond traditional worst-case analysis in different ways; collectively, they appear particularly promising based on recent advances. The first is online algorithms with predictions. Here, the algorithm is augmented with predictions about the unknown future, but the predictions may be noisy in general. The goal is to design online algorithms that automatically take advantage of accurate predictions to go beyond worst-case lower bounds, but at the same time do no worse than traditional online algorithms even if the predictions are arbitrarily inaccurate. This offers a smooth transition between offline and online algorithms based on the quality of information available offline to the algorithm. The second direction is that of online and dynamic algorithms with recourse. Here, the online algorithm is not provided any additional information, but can make a limited number of changes to previous decisions based on newly available information. Again, this offers a smooth transition between offline and online models: if the algorithm is allowed to entirely recompute its solution in every online step, then the model reduces to the offline setting, while it behaves like a traditional online algorithm when it is not given any recourse budget. The final direction is that of online stochastic input models. Here, the algorithm is not evaluated on a worst-case input; rather, one assumes that the input is drawn from some probability distribution which limits the adversary’s ability to produce arbitrary inputs in some way. For instance, it may be the case that the adversary must declare the distribution (but not the input itself) to the algorithm at the very outset, i.e., offline. Or, the input in different steps are drawn independently from an identical distribution; while the algorithm does not know the distribution per se, it has the opportunity to learn in the long run. We hope that by focusing on these themes, the seminar will help set the agenda for online algorithms researchers over the next several years.
Sungjin Im, Nicole Megow, Debmalya Panigrahi, and Sahil Singla
Please log in to DOOR to see more details.
- Anders Aamand (University of Copenhagen, DK) [dblp]
- Spyros Angelopoulos (International Lab on Learning Systems - Montreal, CA) [dblp]
- Antonios Antoniadis (University of Twente, NL) [dblp]
- Yossi Azar (Tel Aviv University, IL) [dblp]
- Eric Balkanski (Columbia University - New York, US) [dblp]
- Niv Buchbinder (Tel Aviv University, IL) [dblp]
- Shuchi Chawla (University of Texas - Austin, US) [dblp]
- Christian Coester (University of Oxford, GB) [dblp]
- José R. Correa (University of Chile - Santiago de Chile, CL) [dblp]
- Andrés Cristi (EPFL - Lausanne, CH) [dblp]
- Sami Davies (University of California - Berkeley, US) [dblp]
- Paul Dütting (Google - Zürich, CH) [dblp]
- Franziska Eberle (TU Berlin, DE) [dblp]
- Marek Elias (Bocconi University - Milan, IT) [dblp]
- Michal Feldman (Tel Aviv University, IL) [dblp]
- Rohan Ghuge (University of Texas - Austin, US) [dblp]
- Anupam Gupta (New York University, US) [dblp]
- Zhiyi Huang (University of Hong Kong, HK) [dblp]
- Sungjin Im (University of California - Santa Cruz, US) [dblp]
- Thomas Kesselheim (Universität Bonn, DE) [dblp]
- Arindam Khan (Indian Institute of Science - Bangalore, IN) [dblp]
- Amit Kumar (Indian Institute of Technology - New Delhi, IN) [dblp]
- Ravi Kumar (Google - Mountain View, US) [dblp]
- Stefano Leonardi (Sapienza University of Rome, IT) [dblp]
- Roie Levin (Rutgers University - New Brunswick, US) [dblp]
- Vasilis Livanos (University of Chile - Santiag de Chile, CL) [dblp]
- Will Ma (Columbia University - New York, US) [dblp]
- Nicole Megow (Universität Bremen, DE) [dblp]
- Marco S. Molinaro (Microsoft Research - Redmond, US & PUC - Rio de Janeiro, BR) [dblp]
- Benjamin J. Moseley (Carnegie Mellon University - Pittsburgh, US) [dblp]
- Seffi Naor (Technion - Haifa, IL) [dblp]
- Debmalya Panigrahi (Duke University - Durham, US) [dblp]
- Vianney Perchet (ENSAE - Palaiseau, FR)
- Rebecca Reiffenhäuser (University of Amsterdam, NL) [dblp]
- Adi Rosén (CNRS - Paris, FR & Université Paris Cité, FR) [dblp]
- Barna Saha (University of California - San Diego, US) [dblp]
- Kevin Schewior (Universität Köln, DE) [dblp]
- Ziv Scully (Cornell University - Ithaca, US) [dblp]
- Golnoosh Shahkarami (MPI für Informatik - Saarbrücken, DE)
- Sandeep Silwal (University of Wisconsin-Madison, US)
- Shikha Singh (Williams College - Williamstown, US) [dblp]
- Sahil Singla (Georgia Institute of Technology - Atlanta, US) [dblp]
- Ola Svensson (EPFL - Lausanne, CH) [dblp]
- Seeun William Umboh (The University of Melbourne, AU) [dblp]
- David Wajc (Technion - Haifa, IL) [dblp]
Classification
- Data Structures and Algorithms
Keywords
- online algorithms
- beyond worst-case algorithm design
- algorithms under uncertainty
