We point two current on-line seminars: Algorithmic Colloquium and TCS+.

- jeudi 8 avril 2021, 14h, zoom, Spyros Angelopoulos puis Nguyen Kim Thang. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
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 6 mai 2021, 14h, zoom, Bruno Escoffier. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
Optimisation multistage on-line

- jeudi 20 mai 2021, 14h, zoom, Christoph Dürr. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09">https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
Un survol sur les boîtes de Pandore, le problème de secrétaire et les inégalités de prophète

- Jeudi 1er avril 2021, 15h, zoom, Hanane Krim. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
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. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
Two-Sided Matching Markets with Correlated Random Preferences

Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal 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 the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The unicity of a stable matching implies non-manipulability, and near-unicity implies limited manipulability, thus these are mathematical properties related to the quality of stable matching algorithms. We study the effect of correlations on approximate manipulability of stable matching algorithms. Our approach is to go beyond worst case, assuming that some of the input preference lists are drawn from a distribution. Our model encompasses a discrete probabilistic process inspired by a popularity model introduced by Immorlica and Mahdian, that provides a way to capture correlation between preference lists. Approximate manipulability is approached from several angles : when all stable partners of a person have approximately the same rank; or when most persons have a unique stable partner. Another quantity of interest is a person's number of stable partners. Our results aim to paint a picture of the manipulability of stable matchings in a ``beyond worst case'' setting.

- lundi 22 mars 2021, 15h, zoom, Francesca Fossati. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
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. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
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 de connecter 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 ainsi que les sommets intermédiaires assurant la connexité des terminaux sont fixes au cours du temps. L'objectif est de trouver l'arbre de poids minimum qui évolue dans le temps en gardant les terminaux connectés. On montre que ce problème est NP-hard même avec seulement deux terminaux et des poids unitaires sur les arêtes, ce qui est l'une des rares versions polynomiales du problème de Steiner dans le cas statique.

- vendredi 19 mars 2021, 11h45, zoom, Mehdi El Krari. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
É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. Lien zoom: https://zoom.us/j/99447957410?pwd=bjR1bG9tYUYybDFoRmowVEJzd2p2UT09
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. Lien zoom: https://us02web.zoom.us/j/4710918755?pwd=K3BoRGthalg1c2hpK3VJOEpYTDkzdz09
Online Search With Maximum Clearance

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

- jeudi 4 mars 2021, 14h30, zoom, Thomas Lidbetter. Lien zoom: https://us02web.zoom.us/j/4710918755?pwd=K3BoRGthalg1c2hpK3VJOEpYTDkzdz09
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. Lien zoom: https://zoom.us/j/94553376689?pwd=LzVZbXhPeFdwb1NlRDR3ZVNtSnBDQT09.
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. Lien zoom: https://zoom.us/j/96236930561?pwd=ZFBLbnpaam02Uy9FTnZMcTRMeXNXUT09.
La propriété de Monge

Dans cet exposé je vais donner une introduction informelle de la propriété de Monge et montrer comment elle peut être exploité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 by Vera Traub, part of the Algorithmic Colloquium (see there the instructions to follow the seminar). We propose to the people who 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 the first constant-factor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it. Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall we improve the approximation ratio from 506 to 22 + ? for any ? > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22.

- lundi 4 mai 2020, 11h, BigBlueButton, David Saulpic
- On the Power of Importance Sampling for Clustering Coreset
Designing coresets for the classic \(k\)-median and \(k\)-means problems with minimal dependency in the number of clusters \(k\), the number of input points \(n\), or the underlying dimension, has been an important 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})\) for doubling metrics, improving upon the recent breakthrough of [Huang et al. 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})\) for Euclidean space, improving on the recent results of [Huang, Vishnoi STOC' 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})\) for general 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, Adrian Vladu, Boston University
- Improved Convergence for L? and L1 Regression via Iteratively
Reweighted Least Squares
The iteratively reweighted least squares method (IRLS) is a popular technique used in practice for solving regression problems. Various versions of this method have been proposed, but theoretical analyses usually fail to capture their good practical performance.

I will present a simple and natural version of IRLS for solving L? and L1 regression, which provably converges to a (1+?)-approximate solution in O(m1/3 log(1/?)/?^(2/3) + log(m/?)/?^2) iterations, where m is the number of rows of the input matrix. This running time is independent of the 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 efficient natural 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 solvers and higher order optimization methods.

- mercredi 20 Novembre 2019, 11h, 26-00/428, Karl Bringmann, Max Planck Institute for Informatics, Saarbrücken
- Fine-grained complexity of subset-sum
- mardi 5 novembre 2019, 11h00 (20 minutes sharp), 26-00/428, David Saulpic
- Near-Linear Time Approximation 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, the
maximum area connected subset problem asks for a subset S of D of size k
maximizing the area of the union of disks in S, under the constraint that
this union is connected. This problem is motivated by wireless router
deployment and is a special case of maximizing a submodular function
under 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-time approximation scheme (PTAS) for this problem with resource augmentation, i.e., allowing an additional set of very few unit disks that are not drawn from the input. Additionally, for two special cases of the problem we 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, Kevin Schewior, ENS
- Prophet Inequalities for
Independent Random Variables from an Unknown Distribution

- mardi 16 avril 2019, 14h, 24-25/405, Nguyen Kim Thang
- Submodular Maximization
Submodular and diminishing-returns (DR) submodular optimization are important optimization problems with many real-world applications in machine learning, economics and communication systems. Moreover, DR-submodular optimization captures a subclass of non-convex optimization that provides both practical and theoretical guarantees.

In this talk, we present algorithms with performance guarantees for the fundamental problems of maximizing non-monotone submodular and DR-submodular functions over convex sets in offline, online and bandit settings. - 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 to solve on some small fraction of inputs, and producing a (sometimes different) problem that is hard to compute on a large fraction of inputs. Hardness amplification is an important step towards understanding average case hardness, and is motivated by modern cryptography. The problems of focus in hardness amplification have typically been non feasible problems, such as problems in EXP and NP. In this talk, we will explore some new arenas in hardness amplification, mainly hardness amplification in P.

Based on joint work with Elazar Goldenberg. - mercredi 12 décembre 2018, 14-16h, 26-00/428, une demie journée d'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és super 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 a relaxation of the classic List-Update Problem (LU) in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the application of track management in Domain Wall Memory. We first show an Omega(log n) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known. We then show that ILU is essentially equivalent to a variation of the Minimum Linear Arrangement Problem (MLA), which we call the Dynamic Minimum Linear Arrangement (DMLA) problem. We then give an offline polynomial-time algorithm for DMLA and show that it has an polylogarithmic approximation guarantee.

This is joint work with Neil Olver, Kirk Pruhs, René Sitters, and Leen Stougie. - 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 (Indian Statistical Institute, Kolkata, India)
- Real Parameter Optimization with Differential Evolution
Differential Evolution (DE) emerged as a simple yet very competitive evolutionary algorithm for optimization over continuous parameter spaces. For more than two decades, DE and its variants (the "DE family" to be precise) have been exhibiting brilliant performance over numerical benchmarks as well as several real world optimization problems. Unlike the traditional evolution strategies or real-coded genetic algorithms, DE does not sample the perturbation step-size for its population members from a parameterized probability distribution. Instead, it uses a kind of self-referential mutation where the scaled vector difference(s) of the current population members are used to perturb others. This talk will discuss the basic working principle of DE and will highlight some of the recent DE variants that are extensively in use for single-objective, multi-modal and non-convex optimization problems. It will also highlight some future research issues including the theoretical studies that need to 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 the
Traveling Thief Problem
Multi-component problems play a crucial role in real-world applications, especially in the area of supply chain management. Recently, the traveling thief problem (TTP) has been introduced to study multi-component problems in a systematic way and many heuristic search algorithms have been proposed for the TTP. Although a lot of algorithmic advances have been made on this problem, determining an optimal solution, even for small instances, is very challenging. In this talk, we will present exact and hybrid approaches for this problem. We start by investigating the already NP-hard Packing While Traveling (PWT) problem which results from TTP when the TSP tour is fixed. We present an exact dynamic programming approach for PWT and give a fully polynomial time approximation 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, we will show how the DP for PWT can be incorporated into an evolutionary multi-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, Aneta Neumann
- Evolutionary Image Composition Using Feature Covariance Matrices
Evolutionary algorithms have recently been used to create a wide range of artistic work. In this paper, we propose a new approach for the composition of new images from existing ones, that retain some salient features of the original images. We introduce evolutionary algorithms that create new images based on a fitness function that incorporates feature covariance matrices associated with different parts of the images. This approach is very flexible in that it can work with a wide range of features and enables targeting specific regions in the images. For the creation of the new images, we propose a population-based evolutionary algorithm with mutation and crossover operators based on random walks. Our experimental results reveal a spectrum of aesthetically pleasing images that can be obtained with the aid of our evolutionary process.

- 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 "Iterative methods in combinatorial optimization" by Lap Chi Lau, R.Ravi and Mohit Singh.

- jeudi 8 mars 2018, 11:00, 26-00/428, Antoine Deza (LRI)
- On lattice polytopes, convex matroid optimization, and degree sequences
of hypergraphs
We introduce a family of polytopes, called primitive zonotopes, which can be seen as a generalization of the permutahedron of type Bd. We discuss connections to the largest diameter of lattice polytopes and to the 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 by showing that deciding whether a given sequence is the degree sequence of a 3-hypergraph is computationally prohibitive. Based on joint works with Asaf Levin (Technion), George Manoussakis (Paris Sud), Syed Meesum (IMSc Chennai), and Shmuel Onn (Technion).

- mardi 27 février 2018, 11:00, 26-00/428, Mikkel Thorup (University of Copenhagen)
- The Power of Theory in the Practice of Hashing with Focus on Similarity
Estimation
Hash functions have become ubiquitous tools in modern data analysis, e.g., the construction of small randomized sketches of large data streams. We like to think of abstract hash functions, assigning independent uniformly random hash values to keys, but in practice, we have to choose a hash function that only has an element of randomness, e.g., 2-independence. While this works for sufficiently random input, the real world has structured data where such simple hash functions fail, calling for the need of more powerful hash functions. In this talk, we focus hashing for set similarity, which is an integral component in the analysis of Big Data. The basic idea is to use the same hash function to do coordinated sampling from different sets. Depending on the context, we want subsets sampled without replacement, or fixed-length vectors of samples that may be with replacement. The latter is used as input to support vector machines (SVMs) and locality sensitive hashing (LSH). The most efficient constructions require very powerful hash functions that are also needed for efficient size estimation. We discuss the interplay between the hash functions and the algorithms using them. Finally, we present experiments on both real and synthetic data where standard 2-independent hashing yield systematically poor similarity estimates, while the right theoretical choice is sharply concentrated, and faster than 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 of distinct-speed robots on an infinite line. In this problem, two mobile robots with different maximal speeds are initially placed at the same point 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. The search is completed when both robots arrive at the exit and the goal is to conclude evacuation in as little time as possible. The robot that discovers the exit first may communicate it to the other robot. We consider two models of communication between the robots, namely wireless communication and face-to-face communication. We present an optimal algorithm for any combination of robot speeds in the case of face-to-face communication. In the case of wireless communication, our algorithm is optimal 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), Yann Strozecki
- Some problems for possible collaboration
I will present different projects I am currently working on and questions I am interested in. I have presented simple stochastic games at seminar S a few month ago, therefore I will focus on periodic scheduling and enumeration algorithms.

- We are working with Nokia to find an efficient way to send messages betweens antennas and data centers periodically over very simple networks while minimizing latency. We have dealt with the case of a star graph and we need to understand better the case of trees and cycles.
- My main subject of research is enumeration algorithm, where the difficulty is to generate a large set of solutions, using as little time 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 about practical 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 with
two unit operations per job
In a so-called mixed-shop scheduling problem, the operations of some jobs 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 the open-shop problem). In this paper we present a new exact polynomial-time algorithm for the mixed-shop problems with preemptions and at most two unit 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 the processing time of a job can potentially be reduced (by an

*a priori*unknown amount) by testing the job. Testing a job \(j\) takes one unit of time and may reduce its processing time from the given upper limit \(\bar{p}_j\) (which is the time taken to execute the job if it is not tested) to any value between \(0\) and \(\bar{p}_j\). This setting is motivated e.g. by applications where a code optimizer can be run on a job before executing it. We consider the objective of minimizing the sum of completion times. All jobs are available from the start, but the reduction 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 job executions adds a novel flavor to the problem. We give first and nearly tight lower and upper bounds on the competitive ratio for deterministic and randomized algorithms. We also show that minimizing the makespan is a considerably easier problem for which we give optimal deterministic and randomized 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 to maintain 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 given problem. In the classical setting, algorithms have access to the entire input and the algorithm is a function applied to this input. The result of the function being the output. In contrast, in the online setting, the input is revealed sequentially, piece by piece; these pieces are called requests. Moreover, after receiving each request, the algorithm must take an action before the next request is revealed. That is, the algorithm must make irrevocable decisions based on the input revealed so far without any knowledge of the future input. Since the future is unknown, these decisions could prove very costly. Online problems have many real-world applications such as paging, routing and scheduling. In this talk, I'll review the topic of online computation, some classic online problems, and some techniques used to analyze online algorithms that have been developed over the last 30 years. Then, I'll show how our new techniques (the bijective ratio and approximate stochastic dominance) fit into this rich domain and apply them to classic problems with a particular focus on the greedy algorithm for the k-server problem, an algorithm that performs well in practice (on certain metric spaces) when the 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 in
Euclidean and minor-free metrics
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in edge-weighted planar graphs; (2) k-median and k-means in edge-weighted planar graphs; (3) k-means in Euclidean space of bounded dimension. Our first and second results extend to minor-closed families of graphs. All our results extend to cost functions that are the p-th power of the shortest-path distance. The algorithm is local search where the local neighborhood of a solution S 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 a
very successful application to the Temporal Knapsack Problem
Dantzig–Wolfe decomposition (or reformulation) is well-known to provide strong dual bounds for specially structured mixed integer programs (MIPs). However, the method was not implemented in any state-of-the-art MIP solver as it is considered to require structural problem knowledge and tailoring to this structure. We provide a computational proof-of-concept that the reformulation can be automated. We demonstrate that for generic MIPs strong dual bounds can be obtained from the automatically reformulated model using column generation. In the second part of the talk we apply a recursive Automatic Dantzig–Wolfe reformulation to the Temporal Knapsack Problem (TKP) which is a generalization of the standard Knapsack Problem where a time horizon is considered, and each item consumes the knapsack capacity during a limited time interval only. We then show that this new method allows us to solve TKP instances to proven optimality through computation of extremely strong 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 of resource-sharing systems that arise in various domains: e.g. inventory management, communication networks. We aim at efficiently allocating the available resources among competing projects according to a certain performance criteria. In particular, we will focus on Restless Bandit (RB) type of allocation problems. These type of problems have a stochastic nature and may be very complex to solve. We will go through different possible techniques to solve RB problems using scaling and relaxation techniques. The latter allow us to obtain simple and ready to implement suboptimal policies. We will discuss on the asymptotic optimality of these policies in interesting regimes such as Heavy-traffic and Light-traffic regimes and also the Many-Users regime. We will provide several application examples for which near-optimal heuristics have been obtained.

- 27 jan 2017, 11:00, Yann Strozecki
- Almost acyclic simple stochastic games
The optimal value computation for turned-based stochastic games with reachability objectives, also known as simple stochastic games, is one of the 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 for instance when the underlying graph is acyclic. I will present three classes of games that can be thought as ”almost” acyclic, by restricting parameters such as the number of cycles or the size of the minimal feedback vertex set. For these classes, we provide several polynomial algorithms or fixed-parameter algorithms.

- 13 jan 2017, 11:00, Siao-Leu Phouratsamay
- Designing contracts in a two-level supply chain with asymmetric
information
We address the problem of coordinating the planning decisions for a single product in a supply chain composed of one supplier and one retailer. We assume that the retailer has private information about his cost structure and that he has the market power, he can impose his optimal replenishment plan. In the case where the actors of the supply chain act individually, the supplier's cost can be large since he has to satisfy the retailer's optimal replenishment plan. However, in order to decrease the supplier's cost, side payment can be allowed between the actors. We propose to design contracts between the actors under the asymmetric information assumption in order to decrease the supplier's cost.

- 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 the complexity issues of the problem. We will present two open questions that still 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 in pattern matching, that of approximating the Hamming distance. Given a pattern P of length n the task is to output an approximation of the Hamming distance (that is, the number of mismatches) between P and every n-length substring of a longer text. We provide the first efficient one-way randomised communication protocols as well as a new, fast and space efficient streaming algorithm for this problem.

- 17 nov 2016, 11:00, Grigorios Koumoutsos
- The (h,k) server problem on bounded-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 or computational jobs) share a single physical machine. Machines are used more efficiently, but tasks' performance deteriorates, as colocated tasks compete for shared resources. As tasks are heterogeneous (CPU-, memory-, network- or disk-intensive), the resulting performance dependencies are complex.

We explore a new resource management model for such colocation. Our model uses two parameters of a task - its size and its type - to characterize how a task influences the performance of the other tasks allocated on the same machine. The performance of a task is a function of the loads of all tasks assigned to the machine. The load of each type is counted separately.

We consider minimization of the total cost (utilitarian fairness). We show that for a linear cost function the problem is strongly NP-hard, but polynomially-solvable in some particular cases. We propose an algorithm polynomial in the number of tasks (but exponential in the number of types and machines); and another algorithm polynomial in the number of tasks and machines (but exponential in the number of types and admissible sizes of tasks). We also propose a polynomial approximation algorithm, and, in a 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; we propose 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 a graph into disjoint clusters, where each cluster forms a clique in the graph, while optimizing some objective function. In online clustering, the input graph is given one vertex at a time, and any vertices that have previously been clustered together are not allowed to be separated. The goal is to maintain a clustering with an objective value close to the optimal solution. For the variant where we want to maximize the number of edges in the clusters, we propose an online strategy based on the doubling technique. It has an asymptotic competitive ratio at most 15.646 and an absolute competitive ratio at most 22.641. We also show that no deterministic strategy can have an asymptotic competitive ratio better than 6. For the variant where we want to minimize the number of edges between clusters, we show that the deterministic competitive ratio of the problem is n-omega(1), where n is the number of vertices in the graph.