|
|
|
|
|
|
dimanche 1 octobre
1
|
lundi 2 octobre
2
|
mardi 3 octobre
3
|
mercredi 4 octobre
4
|
jeudi 5 octobre
5
-
10 h 00 min – 10 h 30 min
Timothé Picavet , «A parameterized approximation scheme for the 2D-Knapsack problem with wide items»
10 h 00 min – 10 h 30 min Timothé Picavet , «A parameterized approximation scheme for the 2D-Knapsack problem with wide items» BAT4 l Séminaire (LIRMM - RDC Entrée) 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.
-
10 h 30 min – 11 h 00 min
Timothé Picavet, «Locally approximating dominating sets in K_{2,t}-minor-free graphs»
10 h 30 min – 11 h 00 min Timothé Picavet, «Locally approximating dominating sets in K_{2,t}-minor-free graphs» BAT4 l Séminaire (LIRMM - RDC Entrée) 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.
|
vendredi 6 octobre
6
|
samedi 7 octobre
7
|
dimanche 8 octobre
8
|
lundi 9 octobre
9
|
mardi 10 octobre
10
|
mercredi 11 octobre
11
|
jeudi 12 octobre
12
-
10 h 00 min – 11 h 00 min
Laure Morelle, «An introduction to odd-minors»
10 h 00 min – 11 h 00 min Laure Morelle, «An introduction to odd-minors» E.3.24 Bâtiment 4 LIRMM 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.
-
14 h 00 min
Emiliano Traversi, «TBA»
14 h 00 min – 14 h 00 min Emiliano Traversi, «TBA» E3.23
|
vendredi 13 octobre
13
|
samedi 14 octobre
14
|
dimanche 15 octobre
15
|
lundi 16 octobre
16
|
mardi 17 octobre
17
|
mercredi 18 octobre
18
|
jeudi 19 octobre
19
-
10 h 00 min – 11 h 00 min
Christophe Paul, «Linear time modular decomposition algorithm»
10 h 00 min – 11 h 00 min Christophe Paul, «Linear time modular decomposition algorithm» salle : E.3.24 Bâtiment 4 LIRMM 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.
-
14 h 00 min
Carla Juvin, «Programmation par contraintes pour le problème de flow-shop robuste à deux machines»
14 h 00 min – 14 h 00 min Carla Juvin, «Programmation par contraintes pour le problème de flow-shop robuste à deux machines» 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.
|
vendredi 20 octobre
20
|
samedi 21 octobre
21
|
dimanche 22 octobre
22
|
lundi 23 octobre
23
|
mardi 24 octobre
24
|
mercredi 25 octobre
25
|
jeudi 26 octobre
26
-
10 h 00 min – 11 h 00 min
Ignasi Sau, «On the number of labeled graphs of bounded clique-width»
10 h 00 min – 11 h 00 min Ignasi Sau, «On the number of labeled graphs of bounded clique-width» salle : E.3.24 Bâtiment 4 LIRMM 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.
|
vendredi 27 octobre
27
|
samedi 28 octobre
28
|
dimanche 29 octobre
29
|
lundi 30 octobre
30
|
mardi 31 octobre
31
|
|
|
|
|
|