Background
The field of learning augmented algorithms is a rapidly developing area at the interface of algorithm design, optimization and machine learning. Traditional algorithmic frameworks typically assume worst-case inputs and evaluate performance under stringent worst-case guarantees. However, in many real-world applications, additional information—often derived from machine-learned predictions—can be leveraged to improve the performance of the algorithms. The challenge lies in designing algorithms that seamlessly integrate such predictions while maintaining mathematical rigor: ensuring comparable worst-case guarantees while achieving near-optimal performance in instances where the predictions are accurate. Striking a balance between consistency and robustness (as it has been termed) has led to fundamental advances in online computation, approximation algorithms and mechanism design. As a result, learning augmented algorithms has emerged as a thriving and influential new direction in modern theoretical computer science.
About the workshop
This four-day workshop will bring together leading researchers of the field to discuss recent advancements, explore key challenges, and foster new collaborations.
The workshop will explore a wide range of topics within learning augmented algorithms, ranging from online algorithms to mechanism design and beyond. The programme will feature four keynote lectures, contributed and lightning talks, and provide ample time for open problem sessions and research discussions.
A key focus of the workshop will be on collaborative problem-solving: during the workshop, a selection of main open problems will be identified, and participants are encouraged to engage in active problem-solving sessions to make progress on these problems each day.
By bringing together a distinguished group of approximately 60 invited researchers, this workshop aims to shape the future of learning augmented algorithms by addressing foundational challenges, encouraging interdisciplinary discussions, and building lasting research collaborations. The event is designed to be highly interactive, ensuring ample time for open problem sessions and informal discussions that can spark new ideas and approaches.
This workshop is co-organized by NETWORKS and supported by NGB, the Dutch OR Society.
Programme
We are delighted that the following four speakers accepted our invitation to give keynote lectures at the workshop:
- Eric Balkanski (Columbia University, USA)
- Marek Eliáš (Bocconi University, Italy)
- Nicole Megow (University of Bremen, Germany)
- Sergei Vassilvitskii (Google Research, USA)
Below is an overview of the invited talks.
The full program is available as pdf: LAA2025-program.pdf
Day 1: Tuesday, 7 October 2025, 13:30-14:30 (online)
Invited Speaker: Sergei Vassilvitskii (Google Research, USA)
Title: New Directions in Algorithms with Predictions
Abstract:
The Algorithms with Predictions area has emerged as a vibrant research area that allows researchers to go beyond worst-case to analyze performance of algorithms and heuristics. In this talk we will review some of the recent work in the area with a specific focus on new directions, including distributional predictions, prediction portfolios, and applications to learning.
Day 2: Wednesday, 8 October 2025, 10:00-11:00
Invited Speaker: Eric Balkanski (Columbia University, USA)
Title: Mechanism Design with Predictions
Abstract:
This talk presents recent advancements in the design of strategyproof mechanisms in the learning-augmented framework. To exhibit the potential benefits of this approach, I will mostly focus on the problem of facility location with strategic agents. In this problem, a set of agents reports their locations in a metric space and the goal is to use these reports to open a new facility, minimizing an aggregate distance measure from the agents to the facility. However, agents are strategic and may misreport their locations to influence the facility's placement in their favor. The aim is to design truthful mechanisms, ensuring agents cannot gain by misreporting. We study both the egalitarian and utilitarian social cost functions, and propose new strategyproof mechanisms that leverage predictions to guarantee an optimal trade-off between consistency and robustness guarantees.
Day 3: Thursday, 9 October 2025, 10:00-11:00
Invited Speaker: Nicole Megow (University of Bremen, Germany)
Title: The Power of Two Oracles: Minimum Spanning Tree and Matroid Optimization
Abstract:
The performance of learning-based algorithms benefits from high-quality predictions, while remaining robust under unreliable predictions. Querying large models such as neural networks can provide highly accurate predictions, but often at significant computational cost. At the same time, lightweight heuristics or smaller models can return approximate information much faster, albeit with reduced reliability. In this talk, we introduce a two-oracle model that formalizes this setting by giving algorithms access to both a fast but noisy oracle and a slow but accurate one, enabling them to balance efficiency and solution quality. We discuss this model in the context of matroid optimization problems, which generalize many classical problems in combinatorial optimization. Our focus is on the maximum-weight basis problem and its special case, the minimum spanning tree. We analyze scenarios involving two different kinds of information: a structural oracle (the independence oracle) and a numerical oracle (weights of elements). We design algorithms that make provably few calls to the clean oracle while remaining robust against arbitrarily poor dirty oracles, thereby approaching the performance of classic algorithms.
Day 4: Friday, 10 October 2025, 10:00-11:00
Invited Speaker: Marek Eliáš (Bocconi University, Italy)
Title: Learning challenges in algorithms with predictions
Abstract:
Learning-augmented algorithms use predictions generated by machine learning models to improve their performance beyond the classical worst-case lower bounds. In this talk, I will discuss various facets of the design of such algorithms which can be framed as learning problems. While the most apparent challenge lies in generating accurate predictions, additional considerations – such as the online estimation of prediction quality and the identification of distinct types of input instances – play an important role in enabling the algorithm to adapt its strategy in the usual setting with unknown prediction error and in scenarios where inputs are drawn from several distinct underlying distributions.
