Calendrier des animations scientifiques

We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal is to pack as many of these rectangles inside the box without overlap. Naturally, this problem is NP-complete. Recently, Grandoni et al. [ESA’19] showed that it is also W[1]-hard when parameterized by the size k of the sought packing, and they presented a parameterized approximation scheme (PAS) for the variant where we are allowed to rotate the rectangles by 90° before packing them into the box. Obtaining a PAS for the original 2D-Knapsack problem, without rotation, appears to be a challenging open question. We make progress towards this goal by showing a PAS under the following assumptions: 1. both the box and all the input rectangles have integral, polynomially bounded sidelengths; 2. every input rectangle is wide — its width is greater than its height; and 3. the aspect ratio of the box is bounded by a constant. Our approximation scheme relies on a mix of various parameterized and approximation techniques, including color coding, rounding, and searching for a structured near-optimum packing using dynamic programming.

The field of distributed algorithms studies algorithms that are designed to run on different computers simultaneously, without any shared memory. We focus on the so-called LOCAL model, where computers are part of a network and work together to solve a problem (in our case Minimum Dominating Set) on the network itself. The LOCAL model is used to study the locality in network computing, to determine which problems can be solved when every computer only knows a part of the network (in our case a constant radius region) before outputting. As finding a constant-factor approximation of MDS is not possible on general graphs, we will focus on minor forbidden classes, particularly the class of $K_{2,t}$-minor-free graphs. We give a $(2t-1)$-approximation for MDS on this class, which breaks the non-exponential approximation factor barrier. This also generalizes and simplifies the involved proof of the 5 approximation factor for outerplanar graphs.

Odd-minors, which are essentially minors preserving the parity of
cycles, are relatively unknown but would gain to be more famous due to
their possible applications to coloring, parameterized complexity, and
structural graph theory, to cite just a few. In particular,
odd-minor-closed graph classes generalize both minor-closed graph
classes and bipartite graphs. We present here known results and
conjectures related to odd-minors, and revisit a graph width parameter
that we dub bipartite treewidth, that seems closely related to odd-minors.

TBA

There is a long history of modular decomposition algorithms starting in the 70’s with a $O(n^4)$ algorithm. The first linear time algorithms appeared in 1994 (by Cournier, Habib and by McConnell, Spinrad). Since them simplified (almost) linear time algorithms have been proposed. I will describe one based on LexBFS and a tree-partition refinement technique. The complexity analysis requires a carefully amortized analysis that we will discuss.

This is a joint work with D. Corneil, M. Habib and M. Tedder that was originally presented at ICALP’08, but which full version is still lacking.

On s’intéresse au problème de flow-shop de permutation à deux machines en tenant compte de durées de traitement incertaines, définies par un budget d’incertitude. Nous montrons dans un premier temps que, sous certaines conditions particulières, le problème peut être résolu en temps polynomial par l’algorithme de Johnson, normalement dédié à la version déterministe du problème. Pour le cas général, nous proposons un modèle de programmation par contraintes, que nous intégrons dans un schéma de décomposition, basé sur la génération de colonnes et de contraintes. Les résultats expérimentaux montrent que cette méthode présente de meilleurs résultats qu’un algorithme de la littérature, basé sur des formulations PLNE.

Clique-width is a graph parameter that has become quite popular due, in particular, to the nice algorithmic properties of the class of graphs for which this parameter is bounded by a constant. In this talk we address the following combinatorial question: which is the (asymptotic) number of $n$-vertex labeled graphs with clique-width at most $k$? We provide lower and upper bounds that leave a quite narrow gap, both for clique-width and for its linear variant. One of our main results is that the number of $n$-vertex labeled graphs with clique-width at most $k$ is $2^{O(kn)}n!$, which is a considerable improvement over the previously best known upper bound $2^{O(k^2 n)}n!$.

Joint work with Marc Noy, Clément Requilé and Giannos Stamoulis.

TBA

TBA

TBA

TBA