Séminaires 2014 - 2015
Sauf mention contraire, le séminaire de Mathématiques Discrètes a lieu le jeudi à 14h30 en Salle C319. Les responsables sont Louis Esperet et András Sebő, n'hésitez pas à les contacter.
- Jeudi 30 avril 2015 (à 14h30):
Eric Tannier (LBBE, Lyon) : Genome rearrangement with variable intergene size distribution
Genome rearrangements are typically modeled by operations acting on permutations of genes with a uniform probability on every operation. I will question this uniformity hypothesis because it does not fit observations and it is not a stable distribution under a rearrangement process on genomes. Simulations show that usual computational or statistical estimators of rearrangement distance are not robust to this generalization. I will propose and test a new statistical estimator based on analogies with random graphs. It approximates the number of pairs of genes that are consecutive in two genomes to an additive sublinear factor, and it is adapted to any intergene size ditribution.
Joint work with Priscila Biller, Nicolas Lartillot, Laurent Gueguen, Carole Knibbe.
- Jeudi 26 mars 2015 (à 14h30):
Jens Vygen (Université de Bonn, Allemagne) : Reassembling Trees for the Traveling Salesman
Many recent approximation algorithms for different variants of the traveling salesman problem (asymmetric TSP, graph TSP, s-t-path TSP) exploit the well-known fact that a solution of the natural linear programming relaxation can be written as convex combination of spanning trees. The main argument then is that randomly sampling a tree from such a distribution and then completing the tree to a tour at minimum cost yields a better approximation guarantee than simply taking a minimum cost spanning tree (as in Christofides' algorithm). We argue that an additional step can help: reassembling the spanning trees before sampling. Exchanging two edges in a pair of spanning trees can improve their properties under certain conditions. We demonstrate the usefulness for the metric s-t-path TSP by devising a deterministic polynomial-time algorithm that improves on Sebo's previously best approximation ratio of 8/5.
- Jeudi 12 mars 2015 (à 14h30):
Guilherme D. da Fonseca (LIRMM, Montpellier) : Linear-Time Approximation Algorithms for Geometric Intersection Graphs
Numerous approximation algorithms for problems on geometric intersection graphs have been proposed in the literature, exhibiting a sharp trade-off between running times and approximation ratios. We introduce a method to obtain linear-time constant-factor approximation algorithms for such problems. To illustrate its applicability, we obtain results for three well-known optimization problems on two classes of geometric intersection graphs. Among such results, our method yields linear-time (4+epsilon)-approximations for the maximum-weight independent set and the minimum dominating set of unit disk graphs, thus bringing dramatic performance improvements when compared to previous algorithms that achieve the same approximation ratios.
Joint work with Vinicius G. Pereira de Sa and Celina M. H. de Figueiredo.
- Jeudi 27 février 2015 (à 10h30):
Seffi Naor (Technion - Israel Institute of Technology) : Simplex Partitioning via Exponential Clocks and the Multiway-Cut Problem
The multiway cut problem is a fundamental graph partitioning problem in which the objective is to find a minimum weight set of edges disconnecting a given set of special vertices called terminals. This problem is NP-hard and there is a well-known geometric relaxation in which the graph is embedded into a high dimensional simplex. Rounding a solution to the geometric relaxation is equivalent to partitioning the simplex. I will discuss a novel simplex partitioning algorithm which is based on two ideas: competing exponential clocks and distortion of the simplex. Unlike previous methods, it utilizes cuts that are not parallel to the faces of the simplex. Applying this partitioning algorithm to the multiway cut problem, a simple 4/3-approximation algorithm is obtained, thus improving upon the current best known result. This bound is further pushed to obtain an approximation factor of 1.32388. It is known that under the assumption of the unique games conjecture, the best possible approximation for the multiway cut problem can be attained via the geometric relaxation.
Joint work with Niv Buchbinder and Roy Schwartz
- Jeudi 12 février 2015 (à 14h30):
Diana Sasaki (LAMSADE, Paris) : Perfect matchings versus maximum weight matchings: the ratio eta for some graph
Motivated by applications in computer graphics, where we seek to convert a triangu- lation into a quadrangulation, Brazil et al. studied the ratio eta between the maximum weight of a perfect matching and the maximum weight of a general matching. Due to the computer graphics application, their study focused mostly on cubic graphs. The parameter eta can be defined for any graph which admits a perfect matching. Therefore, it is natural to consider other graph classes such as grids and regular bipartite graphs. Surprisingly, the determination of eta is often non-trivial even for such restricted types of graphs. In this work, we determine the exact value of eta for all bipartite regular graphs, rectangular grids, bipartite cylindrical grids, and bipartite toroidal grids.
Joint work with Guilherme D. da Fonseca and Bernard Ries.
- Jeudi 29 janvier 2015 (à 14h30):
Aline Parreau (LIRIS, Lyon) : Identifying codes and Vapnik-Chervonenkis dimension
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its closed neighbourhood within the identifying code. Using Vapnik-Chervonenkis dimension, we give a dicothomy result for identifying codes in classes of graphs closed under induced subgraphs: either a class has infinite VC-dimension and has arbitrarly large logarithmic identifying codes or it has finite VC dimension and an identifying code will always be of polynomial size. We also prove that in the first case, the problem of determining the smallest size of an identifying code is hard to approximate within a constant factor. In the second case, this problem can be polynomial-time approximable for some classes like interval graphs for which we provide a 6-approximation algorithm based on linear programming and hard to approximate in other classes.
- Mardi 16 décembre 2014 (à 14h30):
Benjamin Lévêque (LIRMM, Montpellier) : Structure of Schnyder woods in higher genus
We propose a simple generalization of Schnyder woods to higher genus. We give a necessary and sufficient condition for an orientation to corresponds to such a Schnyder wood and we study the structure of these orientations. Unfortunately we are not able to prove the existence of these Schnyder woods in general but a proof for the toroidal case using the structure is proposed.
- Jeudi 4 décembre 2014 (à 14h30):
Aurélie Lagoutte (LIP, ENS Lyon) : From extended formulations of polytopes to the Clique-Stable Set problem
he concept of extended formulations of polytopes was introduced by Yannakakis. A polytope P has a small extended formulation if it is the projection of a polytope Q lying in a higher dimensional space, with a small number of facets. In particular, he studies the stable set polytope and focus on the perfect graphs case, where it can be fully described with the clique constraints. He highlights a lower bound stated as a communication complexity problem: Alice is given a clique K, Bob is given a stable set S, and they have to decide via a non-deterministic protocol whether K intersects S or not. A certificate for the non-intersection is a bipartition of the vertices such that K is included in one side, and S is included in the other side. The goal is to find a Clique-Stable set separator, i.e. a set F of certificates which contains every useful bipartitions, and with |F|=poly(|V(G)|). The question is open in general, and Yannakakis question (i.e. on perfect graphs) is still also open.
We use different techniques to prove that such a polynomial Clique-Stable set separator exists in restricted classes of graphs: probabilistic arguments for random graphs, VC-dimension for graphs where a split graph H is forbidden, the Regularity Lemma and connections with the Erdos-Hajnal property for graphs with no induced path on k vertices and its complement, and decomposition theorem for perfect graphs with no balanced skew partition.
- Jeudi 27 novembre 2014 (à 14h30):
Hyung-Chan An (EPFL, Lausanne) : LP-Based Algorithms for Capacitated Facility Location
Linear programming has played a key role in the study of algorithms for combinatorial optimization problems. In the field of approximation algorithms, this is well illustrated by the uncapacitated facility location problem. A variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to and evolved from algorithms for this problem. Unfortunately, this collection of powerful algorithmic techniques had not yet been applicable to the more general capacitated facility location problem. In fact, all of the known algorithms with good performance guarantees were based on a single technique, local search, and no linear programming relaxation was known to efficiently approximate the problem.
In this paper, we present a linear programming relaxation with constant integrality gap for capacitated facility location. We demonstrate that the fundamental theories of multi-commodity flows and matchings provide key insights that lead to the strong relaxation. Our algorithmic proof of integrality gap is obtained by finally accessing the rich toolbox of LP-based methodologies: we present a constant factor approximation algorithm based on LP-rounding.
Joint work with Mohit Singh and Ola Svensson.
- Mardi 25 novembre 2014 (à 14h30):
Ola Svensson (EPFL, Lausanne) : A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
The last decade has seen an increased interest in generalizations of the secretary problem, a classical online selection problem. These generalizations have numerous applications in mechanism design for settings involving the selling of a good (e.g. ads) to agents (e.g. page views) arriving online. The matroid secretary problem is one of the most well-studied variants. It is general enough to deal with complex settings and, at the same time, it is sufficiently restricted to admit strong algorithms. A famous conjecture states that there is in fact a O(1)-competitive algorithm for the matroid secretary problem. This is an online algorithm that, in expectation and up to a constant factor, performs as well as any offline algorithm with perfect information.
In this talk, we present a new method that improves on the previously best algorithm, in terms of simplicity and its competitive ratio. The main idea of our algorithm is to decompose the problem into a distribution over a simple type of matroid secretary problems which are easy to solve. We show that this leads to a O(loglog(rank))-competitive procedure.
This is joint work with Moran Feldman (EPFL) and Rico Zenklusen (ETHZ).
- Jeudi 6 novembre 2014 (à 14h30):
Marthe Bonamy (LIRMM, Montpellier) : Algorithmes de pré-traitement de graphes
Étant donné un problème paramétré de graphes (partition des sommets en k stables, ou en une forêt et au plus k sommets, détection d'un ensemble dominant de taille k, etc), on s'intéresse à des algorithmes efficaces (i.e. de complexité polynomiale) pour simplifier une instance de ce problème. "Simplifier" peut avoir plusieurs sens selon le résultat désiré. Intuitivement, si on cherche à k-colorier un graphe G, et que ce graphe G contient un sommet de degré au plus k-1, on sait que ce sommet n'aura pas d'influence sur le résultat et peut donc être enlevé du graphe, sans qu'il y ait perte d'information. De même, si ce graphe G contient un sommet qui est adjacent à tous les autres, on sait d'ores et déjà qu'il devra recevoir une couleur distincte de toutes les autres apparaissant sur le graphe, et on peut simplement le supprimer du graphe et chercher à colorier le reste avec seulement k-1 couleurs.
Après avoir identifié un certain nombre de telles règles de simplification, on veut garantir l'efficacité de l'algorithme de pré-traitement correspondant, au moins sur une sous-classe de graphes (par exemple les graphes planaires). Selon le résultat voulu, on peut chercher à montrer que l'algorithme aboutit toujours au graphe vide, ce qui nous assure que la classe de graphes considérée admet toujours une solution (par exemple les graphes planaires pour le problème de 4-coloration). On peut plus généralement chercher à montrer que l'algorithme aboutit toujours à un graphe de taille bornée par une fonction de k, ce qui nous assure que, à k fixé, on peut en temps polynomial décider s'il y a une solution et en trouver une le cas échéant. Ce type de résultat est intéressant en particulier pour des problèmes que l'on sait NP-durs en général.
Ici, on s'intéresse au problème Feedback Vertex Set (combien de sommets doit-on enlever à un graphe pour obtenir une forêt ?) paramétré par la taille de solution (suffit-il d'enlever k sommets ?), dans le cadre des graphes planaires. On présente un algorithme de pré-traitement qui aboutit en temps linéaire à un graphe planaire de taille au plus 13k. Il s'agit d'une collaboration avec Lukasz Kowalik (Université de Varsovie)
- Jeudi 23 octobre 2014 (à 14h30):
Frédéric Maffray (G-SCOP) : Coloration de certains graphes parfaits
Dans un graphe G une paire d'amis est une paire de sommets x et y tels que tous les chemins de x à y sans corde sont pairs. L'utilisation des paires d'amis a permis de fabriquer des algorithmes de coloration efficaces pour diverses classes de graphes parfaits. Dans ce contexte, une conjecture de Reed et Everett est encore ouverte. On présentera des résultats nouveaux dans cette direction, concernant les graphes sans C4.
- Jeudi 2 octobre 2014 (à 14h30):
François Margot (Tepper School of Business, Carnegie Mellon) : Cut generation through binarization
Cutting planes (or cuts) are an essential component of state-of-the-art solvers for Mixed-Integer Linear Program (MILP). Among the many classes of cuts, split cuts are one of the most useful and essential. It is known that split cuts are able to close a large part of the integrality gap for usual benchmark instances, but this requires a large cpu time. Empirical split cut generation aims at generating fast the most useful split cuts. Advances in this direction usually focus on finding strong disjunctions, involving several variables. In this talk, our aim is to use combinations of simple split cuts, i.e. cuts obtained using disjunctions of the form x_j = 0 or x_j = 1 for a binary variable x_j to generate cuts that have similar strength as general split cuts.
Our cut generation scheme is based on two components. First, we use a binarization of general integer variables (i.e., replacing a general integer variable by a sum of binary variables), augmented by additional symmetry breaking constraints. This binarization was introduced by Roy for generating strong Lift-and-Project cuts. Second, we then use rank-2 simple-split cuts, i.e, cuts that can be obtained as a simple split cut for a polyhedron obtained by adding all simple split cuts for the binarization of the problem. We show that for a pure integer problem with two integer variables, these cuts are sufficient to obtain the integer hull of the problem, but that this does not generalize to problems in higher dimensions. We also give an algorithm to compute an approximation of the rank-2 simple split cut closure. We report empirical results on 22 benchmark instances showing that the bounds obtained compare favorably with those obtained with other approximate methods to compute the split closure or lattice-free cut closure. It gives a better bound than the split closure on 6 instances while it is weaker on 9 instances, for an average gap closed 3.8% smaller than the one for the split closure.
Joint work with Pierre Bonami, IBM ILOG CPLEX.