*   Domaine de compétence Optimisation Combinatoire   *
  *    Séminaire
  o    2014 - 2015
  o    2013 - 2014
  o    2012 - 2013
  o    2011 - 2012
  o    2010 - 2011
  o    2009 - 2010
  o    2008 - 2009
  o    2007 - 2008
  o    2006 - 2007
  o    2005 - 2006
  o    2004 - 2005
  o    2003 - 2004
  *    Evénements
  *    Liens

Séminaires 2014 - 2015

Ceci est la page web du séminaire de l'équipe Optimisation Combinatoire du laboratoire G-SCOP, à Grenoble.

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.

16 décembre 2014 Benjamin Lévêque
(LIRMM, Montpellier)
Structure of Schnyder woods in higher genus
4 décembre 2014 Aurélie Lagoutte
(LIP, ENS Lyon)
From extended formulations of polytopes to the Clique-Stable Set problem
27 novembre 2014 Hyung-Chan An
(EPFL, Lausanne)
LP-Based Algorithms for Capacitated Facility Location
25 novembre 2014 Ola Svensson
(EPFL, Lausanne)
A Simple O(loglog(rank))-Competitive Algorithm for the Matroid Secretary Problem
6 novembre 2014 Marthe Bonamy
(LIRMM, Montpellier)
Algorithmes de pré-traitement de graphes
23 octobre 2014 Frédéric Maffray
(G-SCOP)
Coloration de certains graphes parfaits
2 octobre 2014 François Margot
(Tepper School of Business, Carnegie Mellon, USA)
Cut generation through binarization
  • 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.