Satellite workshop 1: Learning augmented algorithms

This workshop is part of the broader CWI research semester programme on learning enhanced optimization, contributing to its overarching mission of advancing cutting-edge research in theoretical computer science, operations research and beyond.

When
7 Oct 2025 from 9:15 a.m. to 10 Oct 2025 7 p.m. CEST (GMT+0200)
Where
Turing Hall, CWI, Science Park 125, Amsterdam, Netherlands.
Add

research-semester-programme-g

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)

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.

Please see below for an overview of the schedule.

The full program is available as pdf: LAA2025-program.pdf

tentative programme
Time Tuesday, 7 Oct Time Wednesday, 8 Oct Thursday, 9 Oct Friday, 10 Oct

9:50-10:20

Registration + Coffee

09:50-10:00

Coffee

Coffee

Coffee

10:20-10:30

Welcome

10:00-11:00

Invited talk: Eric Balkanski

Invited talk: Nicole Megow

Invited talk: Marek Eliáš

10:30-11:30

Introduction Round 1

11:00-11:30

Break

Break

Break

11:30-12:30

Introduction Round 2

11:30-12:30

Contributed talks

Contributed talks

Contributed talks

12:30-13:30

Group photo + Lunch

12:30-13:30

Lunch

Lunch

Closing + Lunch

13:30-14:30

Invited Talk: Sergei Vassilvitskii (online)

13:30-14:30

Open problems and lightning talks

Open problems and lightning talks

-

14:30-15:30

Discussion / lightning talks

14:30-15:30

Discussion / collaboration

Discussion / collaboration

-

15:30-16:00

Break

15:30-16:00

Break

Break

-

16:00-17:00

Contributed talks

16:00-17:00

Contributed talks

Contributed talks

-

17:00-18:30

Borrel

19:00

Social dinner

-

-

Participants

Please note that participation in this workshop is by invitation only! Participation is free of charge, but registration is required. The registration is closed.

The list of participants is given below.

  • Spyros Angelopoulos (CNRS & Sorbonne, France)
  • Antonios Antoniadis (University of Twente, Netherlands)
  • Yossi Azar (Tel-Aviv University, Israel)
  • Eric Balkanski (Columbia University, USA)
  • Evripidis Bampis (Sorbonne, France)
  • Joan Boyar (University of Southern Denmark, Denmark)
  • Kunanon Burathep (Durham University, UK)
  • Ioannis Caragiannis (Aarhus University, Denmark)
  • George Christodoulou (Aristotle University of Thessaloniki, Greece)
  • Vasilis Christoforidis (Aristotle University of Thessaloniki, Greece)
  • Christian Coester (Oxford University, UK)
  • Riccardo Collini Baldeschi (Meta, Italy)
  • Mathis Degryse (CNRS, France)
  • Christoph Dürr (CNRS, France)
  • Marek Eliáš (Bocconi University, Italy)
  • Lene Favrholdt (University of Southern Denmark, Denmark)
  • Vasilis Gkatzelis (Drexel University, USA)
  • Denise Graafsma (University of Twente, Netherlands)
  • Ruben Hoeksma (University of Twente, Netherlands)
  • Giorgos Kalantzis (University of Edinburgh, UK)
  • Danish Kashaev (CWI, Netherlands)
  • Pieter Kleer (Tilburg University, Netherlands)
  • Annamária Kovács (Frankfurt University, Germany)
  • Kim Larsen (University of Southern Denmark, Denmark)
  • Alexandra Lassota (TU Eindhoven, Netherlands)
  • Giorgio Lucarelli (INRIA, France)
  • Bodo Manthey (University of Twente, Netherlands)
  • Nicole Megow (University of Bremen, Germany)
  • Georgii Melidi (Sorbonne, France)
  • Yasamin Nazari (CWI & Vrije Universiteit Amsterdam, Netherlands)
  • Tim Oosterwijk (Vrije Universiteit Amsterdam, Netherlands)
  • Debmalaya Panigrahi (Duke University, USA)
  • Britta Peis (RWTH Aachen, Germany)
  • Manish Purohit (University of Maryland, USA)
  • Gaurav Rattan (University of Twente, Netherlands)
  • Rebecca Reiffenhäuser (University of Amsterdam, Netherlands)
  • Guido Schäfer (CWI & University of Amsterdam, Netherlands)
  • Jens Schlöter (CWI, Netherlands)
  • Alkmini Sgouritsa (Athens University of Economics and Business, Greece)
  • Golnoosh Shakharami (Max Planck Institute for Informatics, Germany)
  • Bertrand Simon (CNRS, France)
  • Martin Skutella (TU Berlin, Germany)
  • Leen Stougie (CWI & Vrije Universiteit Amsterdam, Netherlands)
  • Xizhi Tan (Stanford University, USA)
  • Panagiotis Tsamopoulos (Athens University of Economics and Business, Greece)
  • Artem Tsikiridis (TU Munich, Germany)
  • Marc Uetz (University of Twente, Netherlands)
  • Bart van Parys (CWI, Netherlands)
  • Jesse van Rhijn (University of Twente, Netherlands)
  • Sergei Vassilvitskii (Google Research, USA)
  • Ioannis Vlachos (Athens University of Economics and Business, Greece)
  • Tjark Vredeveld (Maastricht University, Netherlands)
  • Leoni Winschermann (University of Twente, Netherlands)

Organizers

  • Antonios Antoniadis
  • Daniel Dadush
  • Ruben Hoeksma
  • Debankur Mukherjee
  • Guido Schäfer
  • Leen Stougie
  • Marc Uetz
  • Bert Zwart

Accommodation and venue

Please be aware that hotel prices in Amsterdam can be quite steep. We strongly recommend all participants to secure their hotel reservations as early as possible!

Hotel Recommendations

From these hotels, the venue can be reached in 15-30 minutes with public transport. In all public transportation including the train, you can check in and out with a Mastercard or Visa contactless credit card and also with Apple Pay and Google Wallet. At the website of Dutch Railways (NS) https://www.ns.nl/en under FAQ "Travel with your debit card" you can read how it works. Don't forget to check out when you leave bus, tram or the station!

Venue

The conference will be held in the Turing Hall at the Congress Centre of Amsterdam Science Park, next to Centrum Wiskunde & Informatica (CWI).

Address: Science Park 125, 1098 XG Amsterdam

See here for location in Google Maps.

Social event: Dinner on Wednesday 8 October

Restaurant: IJ-Kantine
Address: NSDM-Kade 5, 1033 PG Amsterdam
Time: 19.00h (7.00PM) - 22.30h (10.30PM)

Route from CWI to IJ-Kantine
Take the train from Amsterdam Science Park train station to Amsterdam Central Station.  Science Park train station is about 9 minutes walking from CWI. The train runs 4 times per hour.
At Central Station you have to take the Ferry to the destination NSDM-Werf, that leaves from the backside of Central Station. The trip on the Ferry is for free and takes about 13 minutes. From the destination NSDM-Werf it’s less than 1 minute walking to the Restaurant IJ-Kantine.

CWI research semester programme

This workshop is part of the broader CWI research semester programme on learning enhanced optimization, contributing to its overarching mission of advancing cutting-edge research in theoretical computer science, operations research and beyond.

See here for more information about the whole research semester programme

Financial support

We gratefully acknowledge the financial support of CWI, NETWORKS and NGB, whose contributions helped to make this event possible.

CWI_logo_RGB_rood_1200px

NETWORKS-logo-vierkant

logo-or@2x sponsor

RSP- Learning Enhanced Optimization