This is the page of the seminar S at LIP6, Sorbonne Université, Jussieu. You can subscribe to the annoucement mailing list here. Unless otherwise specified, the tasks will hold in room 26-00/428 at Jussieu, and last for 30 minutes in general (but never more than one hour).

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

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})$$.

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.

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