Past RO Team Seminars

Abstracts of the talks

11 July 2025, Catalin-Viorel Dinu in 26-00/428: An Adaptive Re-evaluation Method for Evolution Strategy under Additive Noise

13 June 2025, Weijie Zheng in 26-00/428

Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency for Many Objectives

The nondominated sorting genetic algorithm II (NSGA-II) is one of the most prominent algorithms to solve multiobjective optimization problems. Despite numerous successful applications, several studies have shown that the NSGA-II is less effective for larger numbers of objectives. In this work, we use mathematical runtime analyses to rigorously demonstrate and quantify this phenomenon. We show that even on the simple m-objective generalization of the discrete OneMinMax benchmark, where every solution is Pareto optimal, the NSGA-II also with large population sizes cannot compute the full Pareto front (objective vectors of all Pareto optima) in subexponential time when the number of objectives is at least three. The reason for this unexpected behavior lies in the fact that in the computation of the crowding distance, the different objectives are regarded independently. This is not a problem for two objectives, where any sorting of a pairwise incomparable set of solutions according to one objective is also such a sorting according to the other objective (in the inverse order).

(This is a joint work with Benjamin Doerr)

06 June 2025, Nowak-Assis Daniel in 26-00/428

Online decision trees for data stream classification

Data stream mining encompasses the development of algorithms capable of extracting patterns from data that arrive constantly and at high speed.

A potentially infinite amount of data requires algorithms to be single-pass, efficient, consider memory constraints, and be adaptive since changes are possible to occur in the data.

In the task of data stream classification, decision trees are one of the most popular algorithms, that owes mostly to the abstract attractiveness of an incremental decision tree,

coupled with their renown performance in ensembles. 20 years of literature in the field will be discussed, from Hoeffding-based trees, known for their periodic splitting mechanism, to the most recently proposed Adaptive-splitting decision trees.

23 May 2025, Hanen Claire in 26-00/428

Kernelization for single machine scheduling with time windows.

Several FPT algorithms have been developed for single machine scheduling problem with time windows. They are build upon structural parameters of the interval graph induced by the time windows : proper level, pathwidh, vertex cover. However, the definition of kernels seems uneasy : how to reduce the number of jobs with respect to the parameter with consistent reduction rules?

We show that for the two first parameters it is unlikely that a polynomial kernel exists, while reduction techniques can be used for the vertex cover parameter, that can also help to reduce the size of the exponential kernels for the two first parameters.

22 May 2025, Raponi Elena in 26-00/428: Bayesian Optimization for Constrained Problems

16 May 2025, Doerr Carola in 26-00/428

07 May 2025, Durand Martin in 26-00/428

Multi-organizational Scheduling: Individual Rationality, Optimality, and Complexity

We investigate multi-organizational scheduling problems. In this setting, multiple organizations each own a set of identical machines and sequential jobs with distinct processing times. The challenge lies in optimally assigning jobs across organizations' machines to minimize the overall makespan while ensuring no organization's performance deteriorates. Our analysis reveals that finding an individually rational schedule with minimum makespan is P^NP[log]-hard, placing it in a complexity class strictly harder than both NP and coNP. We further extend the model by considering an alternative objective: minimizing the sum of job completion times. The corresponding decision variant proves to be NP-complete. Through comprehensive parameterized complexity analysis of both problems, we provide new insights into these computationally challenging multi-organizational scheduling scenarios.

25 April 2025, Escoffier Bruno in 26-00/428: Redistricting : electoral map(s) in France for parliamentary elections

18 April 2025, Guigal Alexis in 26-00/428

11 April 2025, Emmanuel Hyon in 26-00/428

07 April 2025, Duri Andrea JANETT in 26-00/428

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman

We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the first size-depth trade-offs for cutting planes and resolution that are truly supercritical, i.e., in terms of formula size rather than number of variables, and we also show supercritical trade-offs between width and size for treelike resolution. Our results build on a new supercritical width-depth trade-off for resolution, obtained by refining and strengthening the compression scheme for the Cop-Robber game in [Grohe, Lichter, Neuen & Schweitzer 2023]. This yields robust supercritical trade-offs for dimension versus iteration number in the Weisfeiler-Leman algorithm, which also translate into trade-offs between number of variables and quantifier depth in first-order logic. Our other results follow from improved lifting theorems that might be of independent interest.

Based on joint work with Susanna F. de Rezende, Noah Fleming, Jakob Nordström, Shuo Pang

Reference: https://arxiv.org/abs/2411.14267

04 April 2025, Guillaume Aubian (IRIF) in 26-00/428

28 March 2025, Vermetten Diederick in 26-00/428

21 March 2025, Mladenovic Sasa in 26-00/428

07 March 2025, Nguyen DANG + Tai Nguyen (University of St Andrews) in 26-00/428

1st talk [Nguyen DANG] Title: Theory-inspired benchmarks for Dynamic Algorithm Configuration

Many algorithms have their own parameters that can impact the algorithm performance. Automated algorithm configuration (AAC) is a family of general-purpose techniques that focuses on finding the best parameter setting of an algorithm for a given problem. Dynamic algorithm configuration (DAC) is a generalisation of AAC where we want to learn to dynamically change the parameter setting during the solving process. DAC is an emerging area of research and a robust DAC solving technique has yet to be established. In this talk, I will give a very brief overview of those topics and our current work on building theory-inspired benchmarks to support the development of DAC techniques.

>2nd talk [Tai Nguyen]: On the Importance of Reward Design in Reinforcement Learning-based Dynamic Algorithm Configuration

Dynamic Algorithm Configuration (DAC) has garnered significant attention in recent years, particularly in the prevalence of machine learning and deep learning algorithms. Numerous studies have leveraged the robustness of decision-making in Reinforcement Learning (RL) to address the optimization challenges associated with algorithm configuration. However, making an RL agent work properly is a non-trivial task, especially in reward design, which necessitates a substantial amount of handcrafted knowledge based on domain expertise.

In this work, we study the importance of reward design in the context of DAC. Our case study not only demonstrates the ability of RL for this task, but also confirms the importance of reward shaping in the scalability of RL agents.

Based on joint work with Nguyen Dang and Phong Le (both at University of St Andrews), André Biedenkapp (University of Freiburg), and Carola Doerr.

21 February 2025, Fourquet Océane in 26-00/428

Identification of Monotonically Classifying Pairs of Genes for Ordinal Disease Outcomes

In this study, we extend an existing classification method for identifying pairs of genes whose joint expression is associated with binary outcomes to ordinal multi-class outcomes, such as overall survival or disease progression. Our approach is motivated by the need for interpretable classifiers that can provide insights into the underlying biological mechanisms. It can be easily adapted to different research questions, such as identifying gene pair signatures or functional enrichment. We demonstrate that our method is comparable to state-of-the-art classification approaches in terms of performance, while offering the benefit of higher interpretability and adaptability to solve different research questions. Our evaluation on two real-world use cases in glioblastoma and high-grade serous ovarian carcinoma shows that our approach can effectively predict ordinal outcomes and provide novel biological insights.

14 February 2025, Bampis Evripidis in 26-00/428

03 December 2024, Émile Royer in 26-00/428

OnlineSMAC: Bayesian autoML for data streams

Automated machine learning (autoML) methods often require multiple passes over the data and are computationally expensive, making them unsuitable for streaming scenarios where data is continuously generated with evolving distributions over time. The few autoML solutions that have been proposed for stream learning rely on random search and genetic algorithms, which are limited in terms of performance and efficiency in dynamic environments. To address these limitations and the stream requirements, we propose OnlineSMAC, a model-based optimizer for data streams that uses Bayesian optimization and extends the SMAC optimizer to dynamically select the optimal processing pipeline and hyperparameters. Our results show that this new method achieves comparable performance to state-of-the-art online autoML methods.

Joint work with Maroua Bahri.

19 November 2024, Georgii Melidi in 26-00-428

Scenario-Based Robust Optimization of Tree Structures

We initiate the study of tree structures in the context of {\em scenario}-based robust optimization. Specifically, we study Binary Search Trees (BSTs) and Huffman coding, two fundamental techniques for efficiently managing and encoding data based on a known set of frequencies of keys. Given $k$ different scenarios, each defined by a distinct frequency distribution over the keys, our objective is to compute a single tree of best-possible performance, relative to any scenario.

We consider, as performance metrics, the {\em competitive ratio}, which compares multiplicatively the cost of the solution to the tree of least cost among all scenarios, as well as the {\em regret}, which induces a similar, but additive comparison. For BSTs, we show that the problem is NP-hard across both metrics. We also show how to obtain a tree of competitive ratio $\lceil \log_2(k+1) \rceil$, and we prove that this ratio is optimal. For Huffman Trees, we show that the problem is, likewise, NP-hard across both metrics\; we also give an algorithm of regret $\lceil \log_2 k \rceil$, which we show is near-optimal, by proving a lower bound of $\lfloor \log_2 k \rfloor$. Last, we give a polynomial-time algorithm for computing {\em Pareto-optimal} BSTs with respect to their regret, assuming scenarios defined by uniform distributions over the keys. This setting captures, in particular, the first study of {\em fairness} in the context of data structures. We provide an experimental evaluation of all algorithms. To this end, we also provide mixed integer linear program formulation for computing optimal trees.

15 November 2024, Miguel González Duque in 26-00-428

Surveying and benchmarking high-dimensional discrete Bayesian Optimization

This talk provides a broad introduction to high-dimensional Bayesian Optimization (HDBO), and how it is currently being applied to discrete sequence design problems. I present a taxonomy of high-dimensional Bayesian Optimization that slightly updates previous work by Santoni et al., and discuss the latest results in an ongoing benchmark of HDBO methods in black boxes that are relevant in chemistry and biology.

While surveying the field, we realized that methods are frequently tested in heterogeneous and unrealistic set-ups; even more concerning is the fact that the software used to test one optimizer is often incompatible with others. This motivated us to develop poli [1] and poli-baselines [2], which constitute a framework of discrete black box problems and optimizers that can be used in isolation. In this talk I also give a short demo of both libraries.

Interactive survey: https://www.miguelgondu.com/assets/hdbo_timeline.pdf

Preprint: https://arxiv.org/abs/2406.04739

Project website: https://machinelearninglifescience.github.io/hdbo_benchmark/

Links:

------

[1] https://github.com/MachineLearningLifeScience/poli

[2] https://github.com/MachineLearningLifeScience/poli-baselines

05 November 2024, Christoph Dürr in 26-00-428

Aho-Corasick algorithm.

Just for our culture in algorithms: we talk about the problem of find all occurrences of strings w_1,..,w_m in a string s. Running time is linear in the total string length.

22 October 2024, Denis Antipov in 26-00-428

Come to my talk to meet me, a newcomer. I will tell you about the interesting stuff I worked on before joining LIP6. This stuff mostly consists of the theory of evolutionary computation, but in very different aspects: from studying fundamental EAs such as the $(\mu + \lambda)$ to recently emerging areas of diversity optimization and optimization under uncertainty. Definitely, I will brag about my paper which got the best paper award at GECCO 2020 and also about my recent result submitted to AAAI.

I have also participated in some practice/industry-oriented projects, mostly related to mining, space and benchmarking. Although these projects are so far from the runtime analysis (which theory usually does), there are still lots of benefits from having (a) theoretician(s) in the team, and we will discuss why.

08 October 2024, Nilesh Verma in 26-00-428

ASML: A Scalable and Efficient AutoML Solution for Data Streams

Online learning presents a significant challenge to AutoML, as the best model and configuration may change depending on the data distribution. To address this challenge, we propose Automated Streaming Machine Learning (ASML), an online learning framework that automatically finds the best machine learning models and their configurations for changing data streams. ASML adapts to the online learning scenario by continuously exploring a large and diverse pipeline configuration space. It uses an adaptive optimization technique that utilizes the current best design, adaptive random directed nearby search, and an ensemble of best performing pipelines. We experimented with real and synthetic drifting data streams and showed that ASML can build accurate and adaptive pipelines by constantly exploring and responding to changes. In several datasets, it outperforms existing online AutoML and state-of-the-art online learning algorithms.

01 October 2024, Marcus Gallagher in 26-00-428: In this talk I will give a brief overview of my main interests which are in AI, concentrated around the intersection of optimisation and machine learning. I'm visiting Paris from 23rd September - 3rd October and am very interested in discussing mutual research interests. Please send me an email if you would like to have a chat!

24 September 2024, Imène Ait Abderrahim in 26-00-428

In discrete problems, metaheuristic algorithms are traditionally designed following a manual and iterative algorithm development process. The performance of these algorithms is, however, strongly dependent on their correct tuning, including their configuration and parametrization. To overcome manual tuning, automatic algorithm configuration (AAC) is a technique that has shown its efficiency in finding performance-optimizing settings of parameters. However, there is a lot of unexplored potential in AAC, as most algorithms carry out a statically designed algorithm system.

Dynamic algorithm configuration (DAC) is a recent and underexplored research area. It refers to the process of automatically adjusting an algorithm's parameters in real-time based on its performance or changes in the problem environment during execution.

One of the challenges in DAC, especially within the realm of discrete optimization problems, is selecting the most relevant features for the learning process. Features, which describe key aspects of the problem, the state of the algorithm, and the environment, are essential inputs for the DAC system, enabling it to make informed decisions on how to dynamically adjust the algorithm parameters. In discrete optimization, where problem instances vary widely, the right feature selection is crucial for tailoring the algorithm's behavior to specific challenges.

17 September 2024, Vanessa Volz in zoom

There are several aspects of real-world optimization that are not yet well understood or modeled in evolutionary computation (EC) benchmarks. A particularly important one is that, in practice, similar problems are often encountered repeatedly. For example, logistics companies solve comparable routing problems every day, and medical professionals create effective treatment plans on a regular basis. While the underlying problem structures remain unknown, black-box optimization approaches can be iteratively tailored to these regularly encountered problems over time.

My talk will cover our work on introducing this continuous learning setting into existing EC benchmarking frameworks.

10 July 2024, Alex Elenter in 26-00/428

28 June 2024, Denis Antipov in 26-00/428

21 June 2024, Nathan Kirk in zoom: What can machine learning do for quasi-Monte Carlo methods?

19 June 2024, Michalis Xefteris

12 June 2024, Bruno Escoffier

05 June 2024, Mara Santarelli in 26-00/428

22 May 2024, Claire Hanen in 26-00/428: Searching a static target: complexity and algorithms

15 May 2024, Maher Mallem in 26-00/428

06 May 2024, Maroua Bahri in 26-00/428

03 May 2024, André Conde Vázquez

02 May 2024, Shahin Kamali in 26-00/428

10 April 2024, Dimitri Watel in 26-00/428

09 April 2024, Cleophee Robin in zoom

03 April 2024, Matteo Petris in 26-00/428

03 April 2024, Antoine Dailly in zoom, or 26-00/428: Path Covers of Temporal Graphs

27 March 2024, Emmanuel Hyon in 26-00/428

26 March 2024, Vincent Chau in 26-00/428

20 March 2024, Christoph Dürr in 26-00/428

13 March 2024, Camille Grange in 25-26/405: Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems

28 February 2024, Thomas Bellitto in 26-00/428

26 February 2024, Kathrin Klamroth in 26-00/428: Multiobjective Integer Programming in Any Dimension.

21 February 2024, Maria Laura Santoni in 26-00/428

07 February 2024, Dennis Wilson in 26-00/428: Genetic programming for environmental applications

31 January 2024, Oceane Fourquet in 26-00/428: Faster identification of top-performing bivariate monotonic classifiers

13 December 2023, Dimitri Rusin - Learning how to play Othello in 26-00/428

08 December 2023, Deeksha Adil in online/26-00-428

Fast Algorithms for Regression Problems

Increasing data sizes necessitate fast and efficient algorithms for analyzing them. Regression is one such essential tool that is used widely in computer science. In this talk, I will focus on the "p-norm regression problem", which is a generalization of the standard "linear regression problem", and captures several important problems including the maximum flow problem on graphs. Historically, obtaining fast, high-accuracy algorithms for this problem has been challenging due to the lack of smoothness and strong convexity of the function, however, recent breakthroughs have been able to get around these issues. I will present an overview of how these algorithms work and discuss some generalizations of these techniques to other regression problems.

06 December 2023, Koen in 26-00/428: Automated algorithm selection based on problem properties for general black-box optimisation

04 December 2023, Tome Eftimov in zoom, or 26-00/428

Learning for Black-Box Single-Objective Optimization

keywords : black-box optimization, machine learning, algorithm selection, knowledge representation, benchmarking, feature design and selection, ...

15 November 2023, Georgii - Optimal testing procedure for k-out-of-n structures. in 26-00/428

08 November 2023, Christoph in 26-00/428: NP-hardness for weight of inclusion/exclusion in s-t-shortest path

12 October 2023, Günter Rudolf (TU Dortmund) in 26-00/428

Runtime Analysis of (1+1)-EA on a Biobjective Test Function in Unbounded Integer Search Space

Runtime results of multiobjective evolutionary algorithms in unbounded integer spaces are scarce at present. In order to advance this research field we consider two versions of the (1+1)-EA and analyze their runtime to the Pareto front of a carefully designed biobjective test problem.

If time permits, I will also talk about a bicriterial deterministic surrogate model for treating continuous singleobjective problems with stochastic models.

11 October 2023, François Clément in 26-00/428

Constructing Kritzinger Sequences in Low Dimensions

Despite poor performance of greedy L_{\infty} star discrepancy minimization algorithms, Kritzinger recently showed that greedy L_2 star discrepancy minimization produced a seemingly excellent sequence in 1d, with respect to the L_{\infty} star discrepancy. We show empirical evidence supporting the quality of this sequence, outperforming the best known sequences. We will also present some possible directions for the construction of Kritzinger sequences in higher dimensions, in particular dimension 2.

This work is based on discussions with Carola Doerr, Kathrin Klamroth and Stefan Steinerberger.

04 October 2023, Christoph Dürr - Binary search on trees in 26-00/428

We present a result from 2006 by Krzysztof Onak and Paweł Parys, about how to construct an optimal binary search tree for locating a hider in a tree using a minimum number of edge queries.

https://onak.pl/download/publications/Onak_Parys-searching.pdf

27 September 2023, Agustín Caracci (Pontificia Universidad Católica de Chile) in 26-00/428

Searching a polluter on trees

We introduce and study a hide and seek zero-sum game on a tree, where a polluter selects a vertex to hide and an inspector performs k edge queries to find the polluter. Our goal is to find Nash equilibria of this game efficiently. For general trees, we provide a polynomial solution using linear programming techniques. For path graphs, we find a closed expression for the value of the game and an explicit characterization of the optimal strategies used by both players.

This is ongoing work with my advisors José Verschae and Christoph Dürr.

June 23rd 2023 at 11 am, by Anand Srivastav, in room 26-00/428.

Recent Advances in the Maker Breaker Subgraph Game

The triangle game introduced by Chvátal and Erdös (1978) is one of the oldand famous combinatorial games. For n, q ∈ N, the (n, q)-triangle game isplayed by two players, called Maker and Breaker, on the complete graph K_n .Alternately Maker claims one edge and thereafter Breaker claims q edges ofthe graph. Maker wins the game if he can claim all three edges of atriangle. Chvátal and Erdös (1978) proved thatChvátal and Erdös (1978) proved that for q < \sqrt(1/2)\sqrt(n)Maker has a winning strategy, while for for q > 2\sqrt(n)Breaker wins.

Since then, the problem of finding the exactleading constant for the threshold bias of the triangle game has been one of theinteresting open problems in combinatorial game theory. In fact, the constantis not known for any graph with a cycle and we do not even know if such a con-stant exists. Balogh and Samotij (2011) slightly improved the Chvátal-Erdösconstant for Breaker's winning strategy from 2 to 1.935 with a randomizedapproach. Since then no progress was made.

In this work, we present a newdeterministic strategy for Breaker leading to his win, if q > \sqrt(8/3)\sqrt(n).This is almost matching the upper bound of q < \sqrt(1/2)\sqrt(n)for Maker's win, and is a breaktrough after 40 years(Glazik, Srivastav, Europ.J. Comb. 2022.)In previous strategies Breaker chooses his edges such that onenode is part of the last edge chosen by Maker, whereas the remaining node ischosen more or less arbitrarily. In contrast, we introduce a suitable potentialfunction on the set of nodes. This allows Breaker to pick edges that connectthe most 'dangerous' nodes. The total potential of the game may still in-crease, even for several turns, but finally Breaker's strategy prevents the totalpotential of the game from exceeding a critical level and leads to Breaker'swin. We futher survey recent results for cycles of length k, and a generalpotential function theorem (Sowa, Srivastav 2023).

(joint work with Christian Glazik and Mathias Sowa, Kiel University)

May 26th 2023 at 11 am, by Denis Trystram, in room 55-65/211.

Doit-on croire dans le « numérique » pour sortir de la crise climatique ?

Nous vivons actuellement une crise environnementale sans précédent dont le réchauffement climatique est des facettes. Il est aujourd'hui acquis qu'elle est due au développement considérable des activités humaines depuis la fin de la seconde guerre mondiale.La communauté scientifique dans son ensemble a commencé à en prendre conscience, et nombreux sont celles et ceux qui ont intégré cette dimension dans leurs vies quotidiennes et professionnelles.Le « numérique » peut jouer le rôle de levier pour étudier l'efficacité et la complexité des problèmes climatiques. Mais en même temps, le secteur digital constitue une part importante dans les émissions de gaz à effet de serre et est en accélération constante.

Je commencerai cet exposé en esquissant rapidement la dynamique qui conduit aux émissions carbone et son rapport au numérique. Je présenterai également quels outils de mesures qui sont à notre disposition pour évaluer le coût carbone du numérique, en particulier les ACV (analyses de cycle de vie) du matériel informatique et des plates-formes logicielles et les effets rebonds, directs et indirects.

L'objectif principal de cet exposé est de discuter la position de sortie de crise à l'aide du numérique.A travers quelques exemples, j'ouvrirai le débat de la difficulté de dépasser une solution purement technique au service de l'environnement pour apporter des solutions à la hauteur des enjeux globaux.

March 31st 2023 at 2pm by Luca Brunod-Indrigo, in 26-00/428.

Complexity of resource reveling problems

Many scheduling problems involve resources. Those resources are classically associated with hard capacity constraints, as in machine scheduling or RCPSP for instance. In practical applications however, it is often possible to obtain additional resources when needed, yet at a high cost. In the field of scheduling known as resource leveling, irregular resource use is penalized in the objective function in order to model such costs.In this talk, a simple resource leveling criterion is considered as well as classical scheduling constraints and complexity results are given for the corresponding problems. One of the main results, a particular polynomial case, is described in more details.

February 27th 2023 at 2pm by Duri Janett on Monday, in 26-00/428

Tight Runtime Bounds for Static Unary Unbiased Evolutionary Algorithms on Linear Functions.

In this talk, we investigate static unary unbiased Evolutionary Algorithms (EAs). Such EAs can only generate offspring by mutation, i.e., from a single parent. Examples of unary unbiased mutation operators include random local search, standard bit mutation, and fast mutation. Unary unbiased mutation operators are uniquely described by a probability distribution on the set of possible search radii. We give a tight runtime bound for the (1+1)-EA equipped with an (almost) arbitrary but static unary unbiased mutation operator on linear functions, depending on said distribution. This generalizes a seminal result of Witt [CPC '13].

February 1st 2023 at 10:00 by Konstantinos Lakis, in 24-25/405.

How to deliver pizza faster than ever before using ML (or, Learning-Augmented Algorithms for Online TSP on the Line)

Recently, there has emerged a research area called Learning-Augmented Algorithms. The idea is to utilize possibly erroneous predictions about the input of (mainly) Online Problems to circumvent the difficulties associated with the uncertainty therein. One wishes for good performance with perfect predictions (consistency), respectable performance with arbitrarily bad predictions (robustness) and some sort of continuous degradation of performance between the two extremes (smoothness). We focus on the following problem. Imagine yourself in the place of a pizza delivery person with n pizza slices which you are to deliver to n hungry people across some street. These people may call you from any point along this street and at any time. You can give a pizza slice to a person after they have called you by moving to their position. But, your motorbike is limited to unit speed. Your goal is to be done with all the deliveries as soon as possible (we don't care about individual waiting times), where 'done' might (closed variant) or might not (open variant) demand that you finally return to your point of departure. The abstract version of this problem is called Online TSP on the Line. The performance is measured by the competitive ratio (ratio of amounts of time spent) of our algorithm against an optimal offline algorithm (which knows the requests in advance). We augment the setting with predictions about the locations of the requests and obtain consistent, smooth and robust algorithms for both the closed and open variant. For the open variant, we also define a more extensive prediction model which also specifies a request 'best served last' and derive an improved algorithm for this case. For all settings, we also show lower bounds for the consistency value (guaranteed competitive ratio with perfect predictions) of any algorithm, the one for the closed variant being tight.

February 1st 2023 at 10:30 by Golnoosh Shahkarami, in 24-25/405.

A Novel Prediction Setup for Online Speed-Scaling

Given the rapid rise in energy demand by data centers and computing systems in general, it is fundamental to incorporate energy considerations when designing (scheduling) algorithms. Machine learning can be a useful approach in practice by predicting the future load of the system based on, for example, historical data. However, the effectiveness of such an approach highly depends on the quality of the predictions and can be quite far from optimal when predictions are sub-par. On the other hand, while providing a worst-case guarantee, classical online algorithms can be pessimistic for large classes of inputs arising in practice.This paper, in the spirit of the new area of machine learning augmented algorithms, attempts to obtain the best of both worlds for the classical, deadline based, online speed-scaling problem: Based on the introduction of a novel prediction setup, we develop algorithms that (i) obtain provably low energy-consumption in the presence of adequate predictions, and (ii) are robust against inadequate predictions, and (iii) are smooth, i.e., their performance gradually degrades as the prediction error increases.

January 17 2023 at 14:00 by Christoph Dürr, in 25-26/105.

Pricing for Matching

We study the problem of setting prices to items, so to maximize the number of successful transactions for a specific customer model. It consists of a given graph, where items are the vertices, and customers the edges. Every customer wants to buy exactly two specific items and has a budget of 1 Euro. Customer arrival order is adversarial, hence the objective value is the size of the minimum maximal matching in the graph. Now you have the possibility to evict some edges in the graph, by setting the prices, such that for some edges the total price of the endpoints exceeds 1 Euro. The problem consists in choosing prices so to maximize the objective value. I will present some results on this problem.

December 13 2022 at 14:30 by Simon Mauras, online and in 26-00/428.

Truthful Matching with Online Items and Offline Agents (https://arxiv.org/abs/2211.02004)

We study truthful mechanisms for online maximum weight bipartite matching. In our setting, every buyer is associated with a (possibly private) desired set of items, and has a private value for being assigned an item in her desired set. Unlike most online matching settings, where agents arrive online, in our setting the items arrive online in an adversarial order while the buyers are present for the entire duration of the process. This poses a significant challenge to the design of truthful mechanisms, due to the ability of buyers to strategize over future rounds. We provide an almost full picture of the competitive ratios in different scenarios, including myopic vs. non-myopic agents, tardy vs. prompt payments, and private vs. public desired sets. Among other results, we identify the frontier for which the celebrated e/(e-1) competitive ratio for the vertex-weighted online matching of Karp, Vazirani and Vazirani extends to truthful agents and online items.

November 22 2022 at 14:00 in 24-25/405, Magdalena Tydrichova.

The Domain of Euclidean Preferences

This talk is meant to be a gentle introduction to the domain Euclidean preferences. We dispose a set of voters who express their preferences over a set of candidates. These preferences are called Euclidean if voters and candidates can be embedded in a decision space in a way that each voter prefer those candidates closer to him. But what is that decision space? How do we measure the proximity? Can we (easily) recognize a Euclidean profile? And why every profile should definitely want to be Euclidean?

These and other points will be discussed. At the end of the talk, you will not have all the answers - better, you will have many questions to think about.".

October 4 2022 at 14:00 in 24-25/405, Michail Xefteris.

The Canadian Traveller Problem with Predictions

In this talk, we consider the k-Canadian Traveller Problem (k-CTP) under the learning-augmented framework. k-CTP is a generalization of the shortest path problem, and involves a traveller who knows the entire graph in advance and wishes to find the shortest route from a source vertex s to a destination vertex t, but discovers online that some edges (up to k) are blocked once reaching them. In the learning-augmented framework, a potentially imperfect predictor gives us the number and the locations of the blocked edges. We aim at finding (deterministic or randomized) online algorithms that achieve the best possible tradeoff between consistency (quality of the solution when the prediction is correct) and robustness (quality of the solution when there are errors in the prediction).

June 24 2022 at 13:00 in 26-00/428, Nguyen Dang.

A Constraint-Based Tool for Generating Benchmark Instances

Benchmarking is fundamental for assessing the relative performance of alternative solving approaches. For an informative benchmark we often need a sufficient quantity of instances with different levels of difficulty and the ability to explore subsets of the instance space to detect performance discrimination among solvers. In this talk, I will present AutoIG, an automated tool for generating benchmark instances for constraint solvers. AutoIG supports generating two types of instances: graded instances (i.e., solvable at a certain difficult level by a solver), and discriminating instances (i.e., favouring a solver over another). The usefulness of the tool in benchmarking is demonstrated via an application on five problems taken from the MiniZinc Challenges. Our experiments show that the large number of instances found by AutoIG can provide more detailed insights into the performance of the solvers rather than just a ranking. Cases where a solver is weak or even faulty can be detected, providing valuable information to solver developers. Moreover, discriminating instances can reveal parts of the instance space where a generally weak solver actually performs well relative to others, and therefore could be useful as part of an algorithm portfolio.

June 14 2022 at 14:00, room 24-25/405, Aneta Neumann.

Advanced Mine Optimisation under Uncertainty

In many real-world scenarios, it is necessary to handle uncertainty, and potentially disruptive events that violate constraints in stochastic settings need to be avoided. A lot of evolutionary multi-objective algorithms have recently been analyzed and applied to submodular problems with different types of constraints. This talk will provide you insights on the impact of uncertainty in advanced mine optimisation on the real-word stochastic optimisation problem which allow one to mitigate the uncertainty in the deposit while maintaining high profitability. We will also show the behavior of evolutionary multi-objective algorithms on different submodular chance constrained network problems.

June 10 2022 at 14:00, room 24-25/405, Frank Neumann.

Evolutionary Diversity Optimization for Combinatorial Optimization

Diversity plays a crucial role in the area of evolutionary computation. Traditionally, diversity has been used to enable successful crossover operations and prevent premature convergence. In recent years, computing sets of solutions that have structural or behavioural diversity has gained significant attention under the terms evolutionary diversity optimization and quality diversity. This talk will give an overview on this area of research and point out some recent results. We will cover results in the area of evolutionary diversity optimization for the classical traveling salesperson problem and show how quality diversity approaches can be used to achieve better solutions for the traveling thief problem.

May 24 2022 at 13:15, room 25-26/105, Thomas Bellitto.: Geometric graphs and density of sets avoiding distance 1

May 19 2022 at 13:15, room 26-00/428, Niklas Hahn.

Algorithms for Bayesian Persuasion and Delegated Search

We consider a game of strategic communication with asymmetric information between two parties. The uninformed agent chooses an action with an a priori unknown type. This action type determines the individual utility for both agents, who might have very different objectives. Hence, the informed agent tries to influence this decision by sending a signal.

We study this model under the assumption of commitment power, allowing the agent holding it to credibly commit to an action scheme before the state of nature is realized. In Bayesian persuasion, the informed party has commitment power, in delegated search, it is the uninformed party. We try to find (near-)optimal action schemes for the respective party with commitment power in several different settings, some of which can be seen as extensions to the classic prophet inequality and secretary problems.

May 12 2022 at 13:15, room 24-25/405, Shahin Kamali.

Online Algorithms: A Journey from Theory to Practice

This talk will present an overview of recent advances in studying online algorithms. We will use the classic bin packing problem to illustrate alternative models and analysis techniques that yield practical online algorithms. We review modern bin packing applications, such as fault-tolerant server consolidation, and explore the framework of online algorithms with predictions, which has become increasingly influential in the last few years. General themes in this talk include positive versus negative results, analysis techniques that go beyond worst-case, and bridging the gap between theory and practice.

May 11 2022 at 13:15, room 24-25/405, Gokhan Serhat.

Design of nonconventional composite shells using lamination parameters

The use of laminated composite materials has been continuously increasing over the recent decades. This trend also gave rise to the development of different laminate modeling and optimization methods. One particular technique is the lamination parameters, which represent the overall stiffness directionality within the structure. This approach eliminates the solution dependency on the initial assumptions on the laminate configuration and yields convex responses in many cases. It also eases the optimization process by reducing the number of design variables and provides graphical information via contour plots in the feasible domain.In this talk, I will highlight the advantages and limitations of using lamination parameters in the design of nonconventional composite structures. Then, I will summarize my doctoral and postdoctoral studies on this topic. I will wrap up by outlining the major remaining challenges and potential future directions.

April 21 2022 at 13:15, room 24-25/405, Kirill Antonov.: Bayesian Optimization for High-Dimensional Black-Box Optimization

April 14 2021 at 13:15, room 25-26/105, Ana Kostovska.: Ontologies for black-box optimization

March 31 2021 at 13:15, room 24-25/405, Carola Doerr.

Black-Box Optimization: From Theory to Practice

After introducing the key notions and performance measures used in black-box optimization, I will summarize a few of our activities around black-box optimization, carried out in collaboration with different members in the RO team. Our research ranges from theoretical analysis of randomized search heuristics and complexity theory all the way to practical applications that we carry out in collaboration with academic and industrial institutions.

October 15 2021 at 9:30, room 24-25/405, Martin Durand.

Collective schedules : How to find a consensus schedule ?

Given a profile of v schedules representing the preferences of voters on n tasks, we want to find a consensus schedule that aggregates the preferences of the voters. The preference aggregation problem has been widely studied when the candidates that the voters rank are similar. However, in our context, tasks may have different lengths and could therefore be treated differently. We study two classic preference aggregation rules and extend them to fit in our context, we then study their axiomatic and computational properties.

September 15 2021 at 14:00, room 25-26/105 (Grande Salle), Manuel López-Ibáñez.

Incorporating Decision-Maker's Preferences into the Automatic Configuration of Bi-objective Optimisation Algorithms

Automatic configuration (AC) methods are increasingly used to tune and design optimisation algorithms for problems with multiple objectives. Most AC methods use unary quality metrics, such as the hypervolume, to compare the performance of different parameter configurations. These quality metrics, however, imply preferences beyond Pareto-optimality that may differ from those of the decision maker (DM). In this talk, we propose to elicit preferences from the DM by means of the empirical attainment function (EAF) in order to automatically guide the parameter configuration of bi-objective optimisers.Reference: This talk is based on joint work by J.E. Diaz and M. López-Ibáñez published in the European Journal of Operational Research (https://doi.org/10.1016/j.ejor.2020.07.059).

jeudi 17 juin 2021 14h, zoom, Emmanuel Hyon.

Approches par horizon roulant pour un problème de planification stochastique

On s'intéresse à un problème à temps discret dans lequel les táches arrivent de manière aléatoire avec date d'échéance et date de réalisation, une taille et un gain si la táche est traitée.Les slots sont de capacité finies et nous voudrions maximiser les gains apportés par les táches traitées sur un horizon fini. Nous proposons de résoudre ce problème par une approche à horizon roulant.

jeudi 20 mai 2021, 14h, zoom, Christoph Dürr.: Un survol sur les boîtes de Pandore, le problème de secrétaire et les inégalités de prophète

jeudi 6 mai 2021, 14h, zoom, Bruno Escoffier.

Optimisation multistage

L'optimisation multistage s'intéresse à des problèmes dont les données sont susceptiblesd'évoluer dans le temps. Nous considérons dans ce cadre que nous avons une séquence d'instances I_1,...,I_T d'un problème d'optimisation. Nous devons construire une séquence S_1,...,S_T de solutions, en tenantcompte de la présence de coûts de transition pour passer d'une solution S_t à une solution S_{t+1}.

Je présenterai dans cet exposé quelques exemples de résultats de complexité et d'approximation obtenus dans ce cadre.

jeudi 8 avril 2021, 14h, zoom, Spyros Angelopoulos puis Nguyen Kim Thang.

Spyros Angelopoulos: Online Algorithms with predictions

I will give a short overview of some recent work on the recently emerged area of enhancing online algorithms with predictions. In particular, I will discuss problems related to online search and online resource allocation.

Nguyen Kim Thang: Primal-Dual Methods in Online Algorithms with Predictions

In this talk, I will show a primal-dual method aiming to incorporate (machine learning) predictions to online algorithms in order to go beyond the worst-case. Applications will be shown. We will end up with open questions and potential directions for collaborations.

Jeudi 1er avril 2021, 15h, zoom, Hanane Krim.

Titre: Ordonnancement sous contraintes de maintenance préventive et temps de préparation dépendants de la séquence pour minimiser les coûts de rejet ou la somme pondérée des dates de fin.

L'ordonnancement est considéré comme l'une des táches les plus importantes en industrie, notamment dans les ateliers de production. Son but principal est d'allouer les ressources disponibles aux táches sur une période donnée, tout en optimisant un ou plusieurs objectifs tels que la minimisation des délais de production et les coûts de stockage.En France, ces industries contribuent de manière significative à l'économie régionale et nationale, faisant de la région Hauts-de-France la quatrième région économique française. Pour rester compétitives, ces sociétés doivent reposer, d'une part, sur un système de production fiable et disponible à tout moment, et d'autre part, sur de puissants outils d'aide à la décision permettant de réagir rapidement à toute situation imprévue telle qu'une panne ou un retard de livraison de matières premières, des annulations de commandes, etc.Par ailleurs, la maintenance est un autre aspect étroitement lié à l'ordonnancement de la production. L'une des hypothèses les plus courantes dans la littérature est que les machines ou les ressources sont toujours disponibles à tout moment, or, en pratique, il peut être nécessaire de les arrêter en raison de pannes ou de maintenance préventive. Compte tenu du fait que les machines sont un élément essentiel du processus de production et que les coûts de maintenance représentent un grand pourcentage du budget total des opérations, il est souhaitable de bien coordonner la planification de la maintenance et l'ordonnancement de la production.Mes travaux de recherche abordent exactement ce problème, tout en considérant d'autres contraintes comme les temps de préparation dépendant de la séquence. L'objectif principal de ce travail était de concevoir et de développer des méthodes d'optimisation pour l'aide à la décision appliquées aux problèmes d'ordonnancement avec contraintes d'indisponibilité dues à la maintenance préventive. Les modèles et outils proposés sont validés à travers des problèmes académiques et industriels simplifiés. Ceci a conduit au développement de nouveaux algorithmes et modèles basés sur la programmation linéaire en nombres entiers, des heuristiques et des métaheuristiques pour résoudre des problèmes d'ordonnancement de la production.

jeudi 1 avril 2021, 14h, zoom, Simon Mauras.

Two-Sided Matching Markets with Correlated Random Preferences

Stable matching in a community consisting of men and women is aclassical combinatorial problem that has been the subject of intensetheoretical and empirical study since its introduction in 1962 in aseminal paper by Gale and Shapley, who designed the celebrated``deferred acceptance'' algorithm for the problem.

In the input, each participant ranks participants of the opposite type,so the input consists of a collection of permutations, representing thepreference lists. A bipartite matching is unstable if some man-womanpair is blocking: both strictly prefer each other to their partner inthe matching. Stability is an important economics concept in matchingmarkets from the viewpoint of manipulability. The unicity of a stablematching implies non-manipulability, and near-unicity implies limitedmanipulability, thus these are mathematical properties related to thequality of stable matching algorithms.

We study the effect of correlations on approximate manipulability ofstable matching algorithms. Our approach is to go beyond worst case,assuming that some of the input preference lists are drawn from adistribution. Our model encompasses a discrete probabilistic processinspired by a popularity model introduced by Immorlica and Mahdian, thatprovides a way to capture correlation between preference lists.Approximate manipulability is approached from several angles : when allstable partners of a person have approximately the same rank; or whenmost persons have a unique stable partner. Another quantity of interestis a person's number of stable partners. Our results aim to paint apicture of the manipulability of stable matchings in a ``beyond worstcase'' setting.

lundi 22 mars 2021, 15h, zoom, Francesca Fossati.

Novel notions of fairness and resource allocation for congested networked systems

In networking and computing fairness issues come up in resource allocation that is a phase, in a network protocol or system management stack, when a group of individual users or clients have to receive a portion of the resource in order to provide a service. The legacy approach to solve these situations is to consider a single-decision maker problem using classical resource allocation rules as the proportional or the max-min fair one. With the evolution of telecommunication network technologies and thanks to the advances in computing power and software design, new paradigms are emerging and a real-time auditability of the system is possible. In this talk we provide a theoretical and formal analysis of fairness and resource allocation in new technology able to capture the enhanced view users can have on the system when resources are limited and not enough to fully satisfy users' demand. Modeling the resource allocation problem as a bankruptcy game, we define a new measure of users satisfaction together with a new resource allocation and a new measure of fairness. We then investigate how we should move from legacy single-resource approaches to novel multi-resource approaches in order ensure fairness in 5G environments.

lundi 22 mars 2021, 14h, zoom, Mathilde Vernet.

De la complexité du problème de Steiner dynamique / On the complexity of the dynamic Steiner tree problem

Le problème bien connu de l'arbre de Steiner consiste à trouver,dans un graphe donné, un arbre de poids minimum permettant deconnecter un ensemble de sommets appelés terminaux. Cet exposédiscutera de la manière d'étendre ce problème aux graphes dynamiques.Nous considérons des graphes dynamiques dont nous connaissons àl'avance l'évolution et pour lesquels les sommets terminaux ainsique les sommets intermédiaires assurant la connexité des terminauxsont fixes au cours du temps. L'objectif est de trouver l'arbre depoids minimum qui évolue dans le temps en gardant les terminauxconnectés. On montre que ce problème est NP-hard même avec seulementdeux terminaux et des poids unitaires sur les arêtes, ce qui estl'une des rares versions polynomiales du problème de Steiner dans lecas statique.

vendredi 19 mars 2021, 11h45, zoom, Mehdi El Krari.

Études et Analyses de Problèmes d'Optimisation Combinatoire moyennant des Algorithmes Évolutionnaires

Analyser un problème d'optimisation combinatoires (POC) permet de comprendre sa structure et de prédire les meilleures stratégies pour atteindre les meilleures solutions dans les meilleurs délais. Une fonction de hachage a été proposée pour le problème du voyageur de commerce (TSP) et qui permet de différentier les différentes solutions d'une instance avec un nombre de collisions très faible par rapport à la fonction de fitness. Une méthode de réduction pour le TSP généralisé (GTSP) permet de réduire la taille de l'espace de recherche avec des taux de réductions assez importants, permettant ainsi de résoudre les instances dans des délais largement inférieurs par rapport aux instances complètes. Une analyse du paysage de fitness du problème de voleur itinérant (Travelling Thief Problem, TTP) via les réseaux d'optima locaux a permis de comprendre la structure de l'espace de recherche de différentes classes d'instances en fonction des heuristiques de recherche locale sollicitées.

vendredi 19 mars 2021, 10h45, zoom, Thomas Bellitto.

An introduction to forbidden-transition graphs

Graphs have proved to be an extremely useful tool to model routing problems in a very wide range of applications. However, in some of them, we sometimes need to express constraints on the permitted walks that are stronger than what the standard graph model allows for. For example, in a road network, there can be a crossroad where drivers are not allowed to turn right and in this case, many walks in the underlying graph would correspond to routes that a driver is not allowed to use. To overcome this limitation, Kotzig introduced the stronger model of forbidden-transition graphs. A transition is a pair of adjacent edges (or consecutive arcs in the directed case) and a forbidden-transition graph is therefore a graph defined together with a set of pairs of adjacent edges that one may not use consecutively.Because of their expressiveness and practical interest, the study of forbidden-transition graphs is a fast-emerging field but we are still very far from understanding them as well as regular graphs. Problems of routing, connectivity or robustness in those graphs have received growing attention in the last few decades but unfortunately, those problems generally turn out to be algorithmically very difficult, even on restricted subclasses of graphs.In this talk, I will give an introduction to forbidden-transition graphs, present some of the challenges that their study raises and some results I obtained with several co-authors.

jeudi 11 mars 2021, 14h, zoom, Malachi Voss.

Online Search With Maximum Clearance

https://hal.archives-ouvertes.fr/hal-03094824

jeudi 4 mars 2021, 14h30, zoom, Thomas Lidbetter.

A polyhedral approach to some max-min problems

We consider a max-min variation of the classical problem of maximizing a linear function over the base of a polymatroid. In our problem we assume that the vector of coefficients of the linear function is not a known parameter of the problem but is some vertex of a simplex, and we maximize the linear function in the worst case. Equivalently, we view the problem as a zero-sum game between a maximizing player whose mixed strategy set is the base of the polymatroid and a minimizing player whose mixed strategy set is a simplex. We show how to efficiently obtain optimal strategies for both players and an expression for the value of the game. Furthermore, we give a characterization of the set of optimal strategies for Player 2. We discuss the implications of our results for problems in search, sequential testing and queuing. All concepts will be explained in the talk. This is joint work with Lisa Hellerstein.

jeudi 11 février 2021, 14h, zoom, Martin Krejca.

A Study of the Past, Present, and Future Me

Martin Krejca recently joined the RO team as a Post-Doc. In this talk he will present himself and his main research topics.

mardi 8 décembre 2020, 9h30, zoom, Christoph Dürr.

La propriété de Monge

Dans cet exposé je vais donner une introductioninformelle de la propriété de Monge et montrer comment elle peut êtreexploitée pour la programmation dynamique et pour une recherche binaire.

jeudi 1 octobre 2020, 14h.

Due to the current situation, we propose to follow the on-line seminar byVera Traub, part of the Algorithmic Colloquium

(see there the instructions to follow the seminar). We propose to the peoplewho want to see the seminar together to meet in the usual room 26-00/428.

An improved approximation algorithm for ATSP

In a recent breakthrough, Svensson, Tarnawski, and Végh gave thefirst constant-factor approximation algorithm for the asymmetrictraveling salesman problem (ATSP). In this work we revisit theiralgorithm. While following their overall framework, we improve on eachpart of it. Svensson, Tarnawski, and Végh perform several steps ofreducing ATSP to more and more structured instances. We avoid one oftheir reduction steps (to irreducible instances) and thus obtain asimpler and much better reduction to vertebrate pairs. Moreover, weshow that a slight variant of their algorithm for vertebrate pairs hasa much smaller approximation ratio. Overall we improve theapproximation ratio from 506 to 22 + ? for any ? > 0. We alsoimprove the upper bound on the integrality ratio of the standard LPrelaxation from 319 to 22.

lundi 4 mai 2020, 11h, BigBlueButton, DavidSaulpic

On the Power of Importance Sampling for Clustering Coreset

Designing coresets for the classic $k$-median and $k$-meansproblems with minimal dependency in the number of clusters $k$, thenumber of input points $n$, or the underlying dimension, has been animportant research direction over the last 15 years. We present a new,simple, coreset construction that achieves the following bounds:

Size $O(k (d + \log k) \log(1/\varepsilon)\varepsilon^{-6})$ fordoubling metrics, improving upon the recent breakthrough of [Huang etal. FOCS' 18], who presented a coreset with size $O(k^3 d/\varepsilon^2)$.

Size $O(k \log k \cdot \log(1/\varepsilon)\varepsilon^{-6})$ forEuclidean space, improving on the recent results of [Huang, VishnoiSTOC' 20], who presented a coreset of size $O(k\log^2 k\varepsilon^{-4})$.

Size $O(k \log n \cdot \log(1/\varepsilon)\varepsilon^{-6})$ forgeneral discrete metric spaces, improving on the results of [Feldman,Lamberg, STOC'11], who presented a coreset of size $O(k\log n\log k\varepsilon^{-2})$.

Joint work with Vincent Cohen-Addad and Chris Schwiegelshohn

mardi 26 Novembre 2019, 14h, 26-00/428, AdrianVladu, Boston University

Improved Convergence for L? and L1 Regression via IterativelyReweighted Least Squares

The iteratively reweighted least squares method (IRLS) is a populartechnique used in practice for solving regression problems. Variousversions of this method have been proposed, but theoretical analysesusually fail to capture their good practical performance.

I will present a simple and natural version of IRLS for solving L? andL1 regression, which provably converges to a (1+?)-approximate solutionin O(m1/3 log(1/?)/?^(2/3) + log(m/?)/?^2) iterations, where m is thenumber of rows of the input matrix. This running time is independent ofthe conditioning of the input, and up to poly(1/?) beats the O(m1/2)iterations required by standard interior-point methods.

This improves upon the highly specialized algorithms of Chin et al. (ITCS'12), and Christiano et al. (STOC '11), and yields a truly efficientnatural algorithm for the slime mold dynamics (Straszak-Vishnoi, SODA'16, ITCS '16, ITCS '17).

I will also highlight a few connections to packing/covering LP solversand higher order optimization methods.

mercredi 20 Novembre 2019, 11h, 26-00/428, KarlBringmann, Max Planck Institute for Informatics, Saarbrücken: Fine-grained complexity ofsubset-sum

mardi 5 novembre 2019, 11h00 (20 minutes sharp), 26-00/428, David Saulpic: Near-Linear TimeApproximation Schemes for Clustering in Doubling Metrics

mardi 17 Septembre 2019, 11h30, 26-00/428,Mathieu Mari, ENS

Given a set D of n unit disks in the plane and an integer k, themaximum area connected subset problem asks for a subset S of D of size kmaximizing the area of the union of disks in S, under the constraint thatthis union is connected. This problem is motivated by wireless routerdeployment and is a special case of maximizing a submodular functionunder a connectivity constraint.

We prove that the problem is NP-hard and analyze a greedy algorithm,proving that it is a (1/2)-approximation. We then give a polynomial-timeapproximation scheme (PTAS) for this problem with resource augmentation,i.e., allowing an additional set of very few unit disks that are notdrawn from the input. Additionally, for two special cases of the problemwe design a PTAS without resource augmentation.

mardi 4 juin 2019, 13h, 26-00/428, Yakov Zinder,université Technologique de Sydney: Flowshop with buffers

mardi 14 mai 2019, 14h, 24-25/405, KevinSchewior, ENS: Prophet Inequalities forIndependent Random Variables from an Unknown Distribution

mardi 16 avril 2019, 14h, 24-25/405, Nguyen KimThang

Submodular Maximization

Submodular and diminishing-returns (DR) submodular optimization areimportant optimization problems with many real-world applications inmachine learning, economics and communication systems. Moreover,DR-submodular optimization captures a subclass of non-convex optimizationthat provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for thefundamental problems of maximizing non-monotone submodular andDR-submodular functions over convex sets in offline, online and banditsettings.

mercredi 10 avril 2019, 14h, 26-00/428, Karthik C.S.

New Arenas in Hardness Amplification

Hardness amplification is the task of taking a problem that is hard tosolve on some small fraction of inputs, and producing a (sometimesdifferent) problem that is hard to compute on a large fraction of inputs.Hardness amplification is an important step towards understanding averagecase hardness, and is motivated by modern cryptography. The problems offocus in hardness amplification have typically been non feasibleproblems, such as problems in EXP and NP. In this talk, we will exploresome new arenas in hardness amplification, mainly hardness amplificationin P.

Based on joint work with Elazar Goldenberg.

mercredi 12 décembre 2018, 14-16h, 26-00/428, une demie journéed'exposés super courts des thésards et stagiaire: Titres à venir

jeudi 6 décembre 2018, 10-12h, 26-00/428, une demie journée d'exposéssuper courts des permanents et postdoc: Titres à venir

mardi 16 octobre 2018, 14:00, 26-00/428, Kevin Schewior

The Itinerant List-Update Problem

We introduce the Itinerant List-Update Problem (ILU), which is arelaxation of the classic List-Update Problem (LU) in which the pointerno longer has to return to a home location after each request. Themotivation to introduce ILU arises from the application of trackmanagement in Domain Wall Memory. We first show an Omega(log n) lowerbound on the competitive ratio for any randomized online algorithm forILU. This shows that online ILU is harder than online LU, for whichO(1)-competitive algorithms, like Move-To-Front, are known. We then showthat ILU is essentially equivalent to a variation of the Minimum LinearArrangement Problem (MLA), which we call the Dynamic Minimum LinearArrangement (DMLA) problem. We then give an offline polynomial-timealgorithm for DMLA and show that it has an polylogarithmic approximationguarantee.

This is joint work with Neil Olver, Kirk Pruhs, René Sitters, and LeenStougie.

jeudi 14 juin 2018, 14:00, 26-00/418, Nguyen Hung Viet: Different formulations for Max-Cut

mardi 22 mai 2018, 10:30, 26-00/428, Swagatam Das (IndianStatistical Institute, Kolkata, India)

Real Parameter Optimization with Differential Evolution

Differential Evolution (DE) emerged as a simple yet very competitiveevolutionary algorithm for optimization over continuous parameter spaces.For more than two decades, DE and its variants (the "DE family" to beprecise) have been exhibiting brilliant performance over numericalbenchmarks as well as several real world optimization problems. Unlikethe traditional evolution strategies or real-coded genetic algorithms, DEdoes not sample the perturbation step-size for its population membersfrom a parameterized probability distribution. Instead, it uses a kind ofself-referential mutation where the scaled vector difference(s) of thecurrent population members are used to perturb others. This talk willdiscuss the basic working principle of DE and will highlight some of therecent DE variants that are extensively in use for single-objective,multi-modal and non-convex optimization problems. It will also highlightsome future research issues including the theoretical studies that needto be undertaken to fully understand DE.

lundi 14 mai 2018, 11:30, 26-00/428, Frank Neumann

Exact and Hybrid Approaches for Packing While Traveling and theTraveling Thief Problem

Multi-component problems play a crucial role in real-worldapplications, especially in the area of supply chain management.Recently, the traveling thief problem (TTP) has been introduced to studymulti-component problems in a systematic way and many heuristic searchalgorithms have been proposed for the TTP. Although a lot of algorithmicadvances have been made on this problem, determining an optimal solution,even for small instances, is very challenging. In this talk, we willpresent exact and hybrid approaches for this problem. We start byinvestigating the already NP-hard Packing While Traveling (PWT) problemwhich results from TTP when the TSP tour is fixed. We present an exactdynamic programming approach for PWT and give a fully polynomial timeapproximation scheme (FPTAS) for PWT over its baseline travel cost.Afterwards, we extend the approach to give a dynamic programming (DP)approach for TTP and report on some experimental results. Furthermore, wewill show how the DP for PWT can be incorporated into an evolutionarymulti-objective algorithm to tackle a multi-objective formulation of TTP.Joint work with Sergey Polyakovskiy, Martin Skutella, Leen Stougie,Junhua Wu, Markus Wagner

vendredi 11 mai 2018, 11:30, 26-00/428, AnetaNeumann

Evolutionary Image Composition Using Feature Covariance Matrices

Evolutionary algorithms have recently been used to create a wide rangeof artistic work. In this paper, we propose a new approach for thecomposition of new images from existing ones, that retain some salientfeatures of the original images. We introduce evolutionary algorithmsthat create new images based on a fitness function that incorporatesfeature covariance matrices associated with different parts of theimages. This approach is very flexible in that it can work with a widerange of features and enables targeting specific regions in the images.For the creation of the new images, we propose a population-basedevolutionary algorithm with mutation and crossover operators based onrandom walks. Our experimental results reveal a spectrum of aestheticallypleasing images that can be obtained with the aid of our evolutionaryprocess.

jeudi 3 mai 2018, 14:00, 26-00/428, Pierre Fouilhoux: Different characterizations of integral linear programs

jeudi 29 mars 2018, 11:00, 26-00/428, Christoph Dürr

The iterative method

We give a summary of the iterative method from the book "Iterativemethods in combinatorial optimization" by Lap Chi Lau, R.Ravi and MohitSingh.

jeudi 8 mars 2018, 11:00, 26-00/428, Antoine Deza (LRI)

On lattice polytopes, convex matroid optimization, and degree sequencesof hypergraphs

We introduce a family of polytopes, called primitive zonotopes, whichcan be seen as a generalization of the permutahedron of type Bd. Wediscuss connections to the largest diameter of lattice polytopes and tothe computational complexity of multicriteria matroid optimization.Complexity results and open questions are also presented. In particular,we answer a question raised in 1986 by Colbourn, Kocay, and Stinson byshowing that deciding whether a given sequence is the degree sequence ofa 3-hypergraph is computationally prohibitive. Based on joint works withAsaf Levin (Technion), George Manoussakis (Paris Sud), Syed Meesum (IMScChennai), and Shmuel Onn (Technion).

mardi 27 février 2018, 11:00, 26-00/428, Mikkel Thorup (University ofCopenhagen)

The Power of Theory in the Practice of Hashing with Focus on SimilarityEstimation

Hash functions have become ubiquitous tools in modern data analysis,e.g., the construction of small randomized sketches of large datastreams. We like to think of abstract hash functions, assigningindependent uniformly random hash values to keys, but in practice, wehave to choose a hash function that only has an element of randomness,e.g., 2-independence. While this works for sufficiently random input, thereal world has structured data where such simple hash functions fail,calling for the need of more powerful hash functions. In this talk, wefocus hashing for set similarity, which is an integral component in theanalysis of Big Data. The basic idea is to use the same hash function todo coordinated sampling from different sets. Depending on the context, wewant subsets sampled without replacement, or fixed-length vectors ofsamples that may be with replacement. The latter is used as input tosupport vector machines (SVMs) and locality sensitive hashing (LSH). Themost efficient constructions require very powerful hash functions thatare also needed for efficient size estimation. We discuss the interplaybetween the hash functions and the algorithms using them. Finally, wepresent experiments on both real and synthetic data where standard2-independent hashing yield systematically poor similarity estimates,while the right theoretical choice is sharply concentrated, and fasterthan standard cryptographic hash functions with no proven guarantees.

jeudi 14 décembre 2017, 14:00, 26-00/428, Rasmus Ibsen-Jensen: Values and strategies in stochastic games

vendredi 8 décembre 2017, 14:00, 26-00/428, Holger Dell: Finding Detours is Fixed-parameter Tractable

jeudi 16 novembre 2017, 14:00, 26-00/428, Evangelos Bampas

Linear search by a pair of distinct-speed robots

We will present algorithms for the evacuation problem by a pair ofdistinct-speed robots on an infinite line. In this problem, two mobilerobots with different maximal speeds are initially placed at the samepoint on an infinite line. The robots need to find a stationary target(i.e., the exit), which is placed at an unknown location on the line. Thesearch is completed when both robots arrive at the exit and the goal isto conclude evacuation in as little time as possible. The robot thatdiscovers the exit first may communicate it to the other robot. Weconsider two models of communication between the robots, namely wirelesscommunication and face-to-face communication. We present an optimalalgorithm for any combination of robot speeds in the case of face-to-facecommunication. In the case of wireless communication, our algorithm isoptimal if the slow robot is at most 6 times slower than the fast robot.

vendredi 8 septembre 2017, 11:00, 26-00/418 (note the unusual room), YannStrozecki

Some problems for possible collaboration

I will present different projects I am currently working on andquestions I am interested in. I have presented simple stochastic games atseminar S a few month ago, therefore I will focus on periodic schedulingand enumeration algorithms.

We are working with Nokia to find an efficient way to send messagesbetweens antennas and data centers periodically over very simplenetworks while minimizing latency. We have dealt with the case of astar graph and we need to understand better the case of trees andcycles.

My main subject of research is enumeration algorithm, where thedifficulty is to generate a large set of solutions, using as littletime as possible for each solution. I will present the framework,recent complexity results we have obtained and a few open questions.

If time permits, I can speak about other little side projects aboutpractical map isomorphism, hypergraph decomposition ...

Jeudi 13 juillet 2017, 11:00, 25-26/105, Alexander Kononov

A polynomial-time algorithm for the preemptive mixed-shop problem withtwo unit operations per job

In a so-called mixed-shop scheduling problem, the operations of somejobs have to be processed in a fixed order (as in the job-shop problem);the other ones can be processed in an arbitrary order (as in theopen-shop problem). In this paper we present a new exact polynomial-timealgorithm for the mixed-shop problems with preemptions and at most twounit operations per job.

Joint work with Aldar Dugarzhapov.

7 juillet 2017, 11:00, Christoph Dürr

An Adversarial Model for Scheduling with Testing

We consider a novel single-machine scheduling problem where theprocessing time of a job can potentially be reduced (by an apriori unknown amount) by testing the job. Testing a job $j$ takesone unit of time and may reduce its processing time from the given upperlimit $\bar{p}_j$ (which is the time taken to execute the job if it isnot tested) to any value between $0$ and $\bar{p}_j$. This setting ismotivated e.g. by applications where a code optimizer can be run on a jobbefore executing it. We consider the objective of minimizing the sum ofcompletion times. All jobs are available from the start, but thereduction in their processing times as a result of testing is unknown,making this an online problem that is amenable to competitive analysis.The need to balance the time spent on tests and the time spent on jobexecutions adds a novel flavor to the problem. We give first and nearlytight lower and upper bounds on the competitive ratio for deterministicand randomized algorithms. We also show that minimizing the makespan is aconsiderably easier problem for which we give optimal deterministic andrandomized online algorithms.

Joint work with Thomas Erlebach, Nicole Megow, and Julie Meißner.

30 juin 2017, 11:00, Philippe Chrétienne: Complexity of proactive and reactive single machine scheduling tomaintain a maximum number of starting times.

2 juin 2017, 11:00, Emmanuel Hyon: Markov Decision Processes for load balancing

Mercredi 24 mai 2017, 11:00, Marc Renault

Stochastic Dominance and Bijective Analysis of Online Algorithms:Matching theory to practice.

An algorithm is a set of instructions to process the input for a givenproblem. In the classical setting, algorithms have access to the entireinput and the algorithm is a function applied to this input. The resultof the function being the output. In contrast, in the online setting, theinput is revealed sequentially, piece by piece; these pieces are calledrequests. Moreover, after receiving each request, the algorithm must takean action before the next request is revealed. That is, the algorithmmust make irrevocable decisions based on the input revealed so farwithout any knowledge of the future input. Since the future is unknown,these decisions could prove very costly. Online problems have manyreal-world applications such as paging, routing and scheduling. In thistalk, I'll review the topic of online computation, some classic onlineproblems, and some techniques used to analyze online algorithms that havebeen developed over the last 30 years. Then, I'll show how our newtechniques (the bijective ratio and approximate stochastic dominance) fitinto this rich domain and apply them to classic problems with aparticular focus on the greedy algorithm for the k-server problem, analgorithm that performs well in practice (on certain metric spaces) whenthe classic analysis tools claim it should not.

17 mars 2017, 11:00, Vincent Viallat Cohen-Addad

Local search yields approximation schemes for k-means and k-median inEuclidean and minor-free metrics

We give the first polynomial-time approximation schemes (PTASs) forthe following problems: (1) uniform facility location in edge-weightedplanar graphs; (2) k-median and k-means in edge-weighted planar graphs;(3) k-means in Euclidean space of bounded dimension. Our first and secondresults extend to minor-closed families of graphs. All our results extendto cost functions that are the p-th power of the shortest-path distance.The algorithm is local search where the local neighborhood of a solutionS consists of all solutions obtained from S by removing and adding$1/\epsilon^{O(1)}$ centers.

Joint work with Philip N. Klein, and Claire Mathieu.

3 mars 2017, 14:00, Fabio Furini

Automatic Dantzig-Wolfe reformulation of mixed integer programs and avery successful application to the Temporal Knapsack Problem

Dantzig-Wolfe decomposition (or reformulation) is well-known toprovide strong dual bounds for specially structured mixed integerprograms (MIPs). However, the method was not implemented in anystate-of-the-art MIP solver as it is considered to require structuralproblem knowledge and tailoring to this structure. We provide acomputational proof-of-concept that the reformulation can be automated.We demonstrate that for generic MIPs strong dual bounds can be obtainedfrom the automatically reformulated model using column generation. In thesecond part of the talk we apply a recursive Automatic Dantzig-Wolfereformulation to the Temporal Knapsack Problem (TKP) which is ageneralization of the standard Knapsack Problem where a time horizon isconsidered, and each item consumes the knapsack capacity during a limitedtime interval only. We then show that this new method allows us to solveTKP instances to proven optimality through computation of extremelystrong dual bounds.

17 fév 2017, 11:00, Maialen Larrañaga

Restless bandits: Application to resource allocation problems

In this talk we are going to talk about the dynamic control ofresource-sharing systems that arise in various domains: e.g. inventorymanagement, communication networks. We aim at efficiently allocating theavailable resources among competing projects according to a certainperformance criteria. In particular, we will focus on Restless Bandit(RB) type of allocation problems. These type of problems have astochastic nature and may be very complex to solve. We will go throughdifferent possible techniques to solve RB problems using scaling andrelaxation techniques. The latter allow us to obtain simple and ready toimplement suboptimal policies. We will discuss on the asymptoticoptimality of these policies in interesting regimes such as Heavy-trafficand Light-traffic regimes and also the Many-Users regime. We will provideseveral application examples for which near-optimal heuristics have beenobtained.

27 jan 2017, 11:00, Yann Strozecki

Almost acyclic simple stochastic games

The optimal value computation for turned-based stochastic games withreachability objectives, also known as simple stochastic games, is one ofthe few problems in NP ? coNP which are not known to be in P. However,there are some cases where these games can be easily solved, as forinstance when the underlying graph is acyclic. I will present threeclasses of games that can be thought as ”almost” acyclic, byrestricting parameters such as the number of cycles or the size of theminimal feedback vertex set. For these classes, we provide severalpolynomial algorithms or fixed-parameter algorithms.

13 jan 2017, 11:00, Siao-Leu Phouratsamay

Designing contracts in a two-level supply chain with asymmetricinformation

We address the problem of coordinating the planning decisions for asingle product in a supply chain composed of one supplier and oneretailer. We assume that the retailer has private information about hiscost structure and that he has the market power, he can impose hisoptimal replenishment plan. In the case where the actors of the supplychain act individually, the supplier's cost can be large since he has tosatisfy the retailer's optimal replenishment plan. However, in order todecrease the supplier's cost, side payment can be allowed between theactors. We propose to design contracts between the actors under theasymmetric information assumption in order to decrease the supplier'scost.

16 déc 2016, 14:00, Cécile Rottner

Complexity of the min-up/min-down Unit Commitment Problem (MUCP)

We propose several special cases of the MUCP in order to discuss thecomplexity issues of the problem. We will present two open questions thatstill annoy us.

24 nov 2016, 11:00, Tatiana Starikovskaya

Streaming and communication complexity of Hamming distance

We will discuss the complexity of one of the most basic problems inpattern matching, that of approximating the Hamming distance. Given apattern P of length n the task is to output an approximation of theHamming distance (that is, the number of mismatches) between P and everyn-length substring of a longer text. We provide the first efficientone-way randomised communication protocols as well as a new, fast andspace efficient streaming algorithm for this problem.

17 nov 2016, 11:00, Grigorios Koumoutsos: The (h,k) server problem onbounded-depth trees

4 nov 2016, Carola Doerr: Gentle introduction to black-box optimization

28 oct 2016, Krzysztof Rzadca

Colocating tasks in data centers using a side-effects performance model

(joint work with Fanny Pascual)

In data centers, many tasks (services, virtual machines orcomputational jobs) share a single physical machine. Machines are usedmore efficiently, but tasks' performance deteriorates, as colocated taskscompete for shared resources. As tasks are heterogeneous (CPU-, memory-,network- or disk-intensive), the resulting performance dependencies arecomplex.

We explore a new resource management model for such colocation. Our modeluses two parameters of a task - its size and its type - to characterizehow a task influences the performance of the other tasks allocated on thesame machine. The performance of a task is a function of the loads of alltasks assigned to the machine. The load of each type is countedseparately.

We consider minimization of the total cost (utilitarian fairness). Weshow that for a linear cost function the problem is strongly NP-hard, butpolynomially-solvable in some particular cases. We propose an algorithmpolynomial in the number of tasks (but exponential in the number of typesand machines); and another algorithm polynomial in the number of tasksand machines (but exponential in the number of types and admissible sizesof tasks). We also propose a polynomial approximation algorithm, and, ina case of a single type, a polynomial exact algorithm. For convex costs,we prove that, even for a single type, the problem becomes NP-hard; wepropose an approximation algorithm.

14 oct 2016, Christoph Dürr

Competitive Strategies for Online Clique Clustering

Clique clustering is the problem of partitioning the vertices of agraph into disjoint clusters, where each cluster forms a clique in thegraph, while optimizing some objective function. In online clustering,the input graph is given one vertex at a time, and any vertices that havepreviously been clustered together are not allowed to be separated. Thegoal is to maintain a clustering with an objective value close to theoptimal solution. For the variant where we want to maximize the number ofedges in the clusters, we propose an online strategy based on thedoubling technique. It has an asymptotic competitive ratio at most 15.646and an absolute competitive ratio at most 22.641. We also show that nodeterministic strategy can have an asymptotic competitive ratio betterthan 6. For the variant where we want to minimize the number of edgesbetween clusters, we show that the deterministic competitive ratio of theproblem is n-omega(1), where n is the number of vertices in the graph.