RO Team Seminars Series: Autumn 2025

When? On Fridays at 14:00, starting from October. A backup time is on Thursdays, also at 14:00. All talks will be added to the calendar which you can subscribe to using this link.

Where? Room 26-00.428 at Jussieu campus. And also in Zoom, but only by request (by default we do not start the online meeting).

Contact organizer: Denis Antipov.

Abstracts of the talks (in retrospective)

11 February at 14:00, by Denis Antipov, in room 26-00/428.

When Switching Algorithms Helps: A Theoretical Study of Online Algorithm Selection

Online algorithm selection (OAS) aims to adapt the optimization process to changes in the fitness landscape and is expected to outperform any single algorithm from a given portfolio. Although this expectation is supported by numerous empirical studies, there are currently no theoretical results proving that OAS can yield asymptotic speedups. Moreover, theory-based guidelines for when and how to switch between algorithms are largely missing.

In this talk, we present the first theoretical example in which switching between two algorithms—the (1 + λ) EA and the (1 + (λ, λ)) GA—solves the OneMax problem asymptotically faster than either algorithm used in isolation. We show that an appropriate choice of population sizes for the two algorithms allows the optimum to be reached in O(nloglog(n)) expected time, faster than the ≈Ω(n√logn) runtime of the best of these two algorithms with optimally tuned parameters.

We first establish this bound under an idealized switching rule that changes from the (1 + λ) EA to the (1 + (λ, λ)) GA at the optimal time. We then propose a realistic switching strategy that achieves the same performance. Our analysis combines fixed-start and fixed-target perspectives, illustrating how different algorithms dominate at different stages of the optimization process. This approach offers a promising path toward a deeper theoretical understanding of OAS.

6 February at 14:00, by Meike Neuwohner, in room 26-00/428.

A Better-Than-2 Approximation for the Directed Tree Augmentation Problem

We introduce and study a directed analogue of the weighted Tree Augmentation Problem (WTAP). In the weighted Directed Tree Augmentation Problem (WDTAP), we are given an oriented tree T = (V, A) and a set of directed links L ⊆ V × V with positive costs. The goal is to select a minimum cost set of links which enters each fundamental dicut of T (cuts with one leaving and no entering tree arc). WDTAP captures the problem of covering a cross-free set family with directed links. It can also be used to solve weighted multi 2-TAP, in which we must cover the edges of an undirected tree at least twice. WDTAP can be approximated to within a factor of 2 using standard techniques. We provide an improved (1.75 + ε)-approximation algorithm for WDTAP in the case where the links have bounded costs, a setting that has received significant attention for WTAP. To obtain this result, we discover a class of instances, called "willows", for which the natural set covering LP is an integral formulation. We further introduce the notion of "visibly k-wide" instances which can be solved exactly using dynamic programming. Finally, we show how to leverage these tractable cases to obtain an improved approximation ratio via an elaborate structural analysis of the tree.

This result is joint work with Olha Silina and Michael Zlatin and appeared in the proceedings of SODA 2026.

2 February 2026 at 11:00, by Annelot Bosman, in room 26-00/428.

A birds-eye view of robustness in neural networks

In recent years, despite the remarkable performance of neural networks in various tasks, their vulnerability to adversarial perturbations has led to concerns about the reliability and security of these models. Adversarial perturbations are small, imperceptible modifications to inputs that lead to misclassifications. This rising concern is reflected in the sizeable body of scientific work investigating different kinds of attacks training neural networks to be robust against perturbations and formal verification of different robustness properties. A prominent example of such a property is local robustness, which determines for a given network and input whether the network is robust against input perturbations up to a certain magnitude. In this talk we will discuss how these perturbations work, how to quantify the robustness of a neural network and other research.

30 January 2026 at 11:30, by Christoph Dürr, in room 26-00/428.

Two Complexity Results on Spanning-Tree Congestion Problems

In the spanning-tree congestion problem (STC), we are given a graph G, and the objective is to compute a spanning tree of G that minimizes the maximum edge congestion. While STC is known to be NP-hard, even for some restricted graph classes, several key questions regarding its computational complexity remain open, and we address some of these in our paper. (i) For graphs of degree at most d, it is known that STC is NP-hard when d≥8. We provide a complete resolution of this variant, by showing that STC remains NP-hard for each degree bound d≥3. (ii) In the decision version of STC, given an integer K, the goal is to determine whether the congestion of G is at most K. We prove that this variant is polynomial-time solvable for K-edge-connected graphs.

Joint work with Sunny Atalig, Marek Chrobak, Petr Kolman, Huong Luu, Jiří Sgall, Gregory Zhu.

23 January 2026 at 11:00, by Bruno Escoffier, in room 26-00/428.

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems

We consider a learning-augmented framework for NP-hard permutation problems. The algorithm has access to predictions telling, given a pair u,v of elements, whether u is before v or not in an optimal solution. Building on the work of Braverman and Mossel (SODA 2008), we show that for a class of optimization problems including scheduling, network design and other graph permutation problems, these predictions allow to solve them in polynomial time with high probability, provided that predictions are true with probability at least 1/2+ε.

Joint work with E. Bampis, D. Fotakis, P. Patsilinakos, M. Xefteris

10 December 2025 at 15:00, by Aris Pagourtzis, in room 26-00/428.

Finite Pinwheel Scheduling: the k-Visits Problem

Pinwheel Scheduling is a fundamental scheduling problem, in which each task is associated with a positive integer d_i, and the objective is to schedule one task per time slot, ensuring each task perpetually appears at least once in every d_i time slots. Although conjectured to be PSPACE-complete, it remains open whether Pinwheel Scheduling is NP-hard (unless a compact input encoding is used) or even contained in NP

In this work we introduce k-Visits, a finite version of Pinwheel Scheduling, where given n deadlines, the goal is to schedule each task exactly k times. While we observe that the 1-Visit problem is trivial, we prove that 2-Visits is strongly NP-complete through a surprising reduction from Numerical 3-Dimensional Matching (N3DM). As intermediate steps in the reduction, we define NP-complete variants of N3DM which may be of independent interest. We further extend our strong NP-hardness result to a generalization of k-Visits k≥2 in which the deadline of each task may vary throughout the schedule, as well as to a similar generalization of Pinwheel Scheduling, thus making progress towards settling the complexity of Pinwheel Scheduling.

Additionally, we prove that 2-Visits can be solved in linear time if all deadlines are distinct, rendering it one of the rare natural problems which exhibit the interesting dichotomy of being in P if their input is a set and NP-complete if the input is a multiset. We achieve this through a Turing reduction from 2-Visits to a variation of N3DM, which we call Position Matching. Based on this reduction, we also show an FPT algorithm for 2-Visits parameterized by a value related to how close the input deadlines are to each other, as well as a linear-time algorithm for instances with up to two distinct deadlines.

Joint work with Sotiris Kanellopoulos, Christos Pergaminelis, Maria Kokkou, and Euripides Markou. To appear in SODA 2026. Available at arxiv

5 December 2025 at 14:00, by Justine Cauvi, in room 26-00/428..

Temporal graphs : parameters, labelings and realizations

A temporal graph can be defined as a labeled graph, in which the labels on an edge correspond to its appearance times. Connectivity in this context is more naturally grasped by temporal paths, that is, paths where edges are traversed one after another in time. This definition of temporal path leads to several notions of distance, when the length of the path is measured in terms of its number of edges, or its arrival time (i.e. the appearance of the last edge), or its duration (i.e. the appearance difference between the last edge and the first edge). An interesting variant of a temporal path is a restless temporal path, that is a temporal path in which the waiting time at each node is restricted.

In this talk, I will present three different problems on temporal graphs. First, I will show results on the restless temporal path problem parameterized by a newly introduced temporal parameter. I will then discuss some results on the design of labeling schemes in order to retrieve the minimum duration, the minimum number of hops or the earliest arrival time of a temporal path from a node to another. Finally, I will present results on the temporal realization problem in which, given an n × n matrix D, one asks if there exists a temporal graph G of n nodes such that the entry at line i and column j of the matrix corresponds to the minimum number of edges (or arrival time/duration depending on the distance variant) of a temporal path in G from i to j.

28 November 2025 at 14:00, by Tomasz Kanas, in room 26-00/428.

Approximation algorithms for scheduling serverless invocations

Serverless products, such as Function-as-a-Service, are relatively new cloud offerings. It allows users to conveniently develop cloud applications by uploading their code directly to the cloud, instead of managing containers or VMs. However, this leads to splitting the logic into many small functions, and every one needs to be deployed to the proper environment by the provider before the invocation, which may take even longer than the invocation itself.

I will present our results on approximation algorithms aimed at scheduling those invocations. We have modelled it as an offline scheduling with setup times problem, with the added assumption that the setup times are proportionally long compared to the task lengths. I will also show some preliminary results of our new approach - using a stochastic queueing model.

21 November 2025 at 14:00, by Jonas Kuckling, in room 26-00/428.

Optimization-based design of control software for robot swarms

Swarm robotics is a paradigm to organize decentralized large-scale multi-robot systems. Within this framework, the collective behavior of the swarm does not arise from centralized programming, but rather emerges through the interactions of individual robots. The great number of often unpredictable interactions poses one of the main challenges of designing control software for robot swarms. To address this complexity, automated methods reframe the design problem as an optimization task, employing techniques such as evolutionary computation or reinforcement learning. In this presentation, I will discuss the challenges associated with optimization-based design in swarm robotics and provide an overview on my related, ongoing research.

14 November 2025 at 14:00, by Thomas Bellitto, in room 24-25/405.

The smallest 5-chromatic tournament

A tournament is an oriented graph such that for every two vertices u and v, there exists exactly one arc between u and v. A tournament is called transitive or acyclic if for every arc (u,v) and (v,w), the arc between u and w is from u to w. Neumann-Lara asked for the size of the smallest tournamnet that cannot be partitioned into 4 transitive subtournaments and conjectured in 1994 that the answer is 17.

In this talk, we will give a brief introduction to the field of Ramsey theory. We will then see how Neumann-Lara's problem is connected to both Ramsey theory and graph coloring. Finally, we will present our answer to the problem.

24 October 2025 at 14:00, by Imène Ait abderrahim, in room 26-00/428.

Ant Colony Optimization for Operating Room Scheduling: Improved Efficiency and Resource Management

The scheduling of surgical interventions greatly impacts the capacity of medical centers to treat patients with available operating room resources. Traditional manual scheduling often fails to meet demand, leading to longer waiting lists. Effective scheduling must not only create a feasible timetable but also prioritize patients based on medical urgency. The Operating Room Scheduling Problem (ORSP) is a complex combinatorial optimization challenge characterized by constraints such as the availability of operating rooms, surgical staff, and medical equipment, as well as factors like surgical priorities, procedure durations, and postoperative recovery needs. We propose an Ant Colony Optimization (ACO) approach for the ORSP that takes into consideration the urgency of surgeries by calculating their priorities. Numerical experiments were conducted on five test cases from the literature of varying sizes and resource availability, in addition to 3 cases from a real-world schedule obtained from a Hospital in Algeria. The results demonstrate that our proposed ACO algorithm outperformed the literature results in terms of makespan, overtime, and the variation coefficient of working time of the used resources.

17 October 2025 at 14:00, by Vitor Basto Fernandes, in room 26-00/428.

Data Management in Black-Box Optimization Research

The black-box optimization research community has recently identified and made explicit in scientific fora, the need for systematic, formal and open data management practices in this research field. Benchmarking data are generally not well structured, defined, or harmonized, for example, they suffer from the use of different taxonomies, nomenclatures, data representations, etc. This renders performance comparison and validation difficult or impossible, hindering the development and progress of this scientific area. Initiatives such as IOHprofiler, OPTION and the Optimisation Problem Library, address some dimensions of this problem. In a different scale and abstraction level, EU Data Strategy policies, initiatives, infrastructures, services and tools, such as the Research and Innovation Common European Data Space and the European Open Science Cloud - OpenAIRE, are actively promoting research data management best practices. We propose a roadmap for black-box optimization research data management to integrate with the EU Data Strategy agenda, benefiting from and contributing to the EU open science large-scale infrastructures, services, tools, standardization processes, and best practices. Our key goal is to make a step forward towards FAIR (findable, accessible, interoperable and reusable) research results in the black-box optimization research domain.

Joint work with Carola Doerr and Diederick Vermetten.

10 October 2025 at 14:00, by Lars Kotthoff, in room 26-00/428.

Code Evolution Graphs: Understanding Large Language Model Driven Design of Algorithms

Large Language Models (LLMs) have demonstrated great promise in generating code, especially when used inside an evolutionary computation framework to iteratively optimize the generated algorithms. However, in some cases they fail to generate competitive algorithms or the code optimization stalls, and we are left with no recourse because of a lack of understanding of the generation process and generated codes. We present a novel approach to mitigate this problem by enabling users to analyze the generated codes inside the evolutionary process and how they evolve over repeated prompting of the LLM. We show results for three benchmark problem classes and demonstrate novel insights. In particular, LLMs tend to generate more complex code with repeated prompting, but additional complexity can hurt algorithmic performance in some cases. Different LLMs have different coding “styles” and generated code tends to be dissimilar to other LLMs. These two findings suggest that using different LLMs inside the code evolution frameworks might produce higher performing code than using only one LLM.

Joint work with Niki van Stein, Anna Kononova, and Thomas Bäck.

3 October 2025 at 14:00, by Christoph Dürr, in room 26-00/428.

Decision-Theoretic Approaches for Improved Learning-Augmented Algorithms

We initiate the systematic study of decision-theoretic metrics in the design and analysis of algorithms with machine-learned predictions. We introduce approaches based on both deterministic measures such as distance-based evaluation, that help us quantify how close the algorithm is to an ideal solution, and stochastic measures that balance the trade-off between the algorithm's performance and the risk associated with the imperfect oracle. These approaches allow us to quantify the algorithm's performance across the full spectrum of the prediction error, and thus choose the best algorithm within an entire class of otherwise incomparable ones. We apply our framework to three well-known problems from online decision making, namely ski-rental, one-max search, and contract scheduling.

joint work with Spyros Angelopoulos and Georgii Melidi