Séminaires 2012 - 2013

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 Andras Sebö, n'hésitez pas à les contacter.

• Mardi 16 juillet 2013 (à 14h30): Viktoria Kaszanitzky (Université Eotvos, Budapest) : Symmetry-forced rigidity in the plane
  
  We consider planar bar-and-joint frameworks with discrete point group symmetry in which the joint positions are as generic as possible subject to the symmetry constraint. We provide combinatorial characterizations for symmetry-forced rigidity of such structures with cyclic or odd-order dihedral symmetry.
  
  Joint work with T. Jordan and S. Tanigawa.
  
  
• Vendredi 13 juin 2013 (à 14h30): Andrea Munaro (Université de Bonn, Allemagne) : On the VC-Dimension of a Hypergraph
  
  The VC-dimension of a hypergraph represents a prominent measure of its "complexity". The class of hypergraphs with VC-dimension less than k can be viewed as the class of hypergraphs with a certain forbidden trace, namely the complete hypergraph on k vertices. We present a linear algebraic method that is useful to address the following Turan-type problem: What is the maximum number of edges in a hypergraph on [n] with VC-dimension less than k?
  
  Moreover, given a graph G, we consider set systems on V(G) induced by certain families of its subgraphs. In this way we obtain several different notions of VC-dimension, each one related to a special family of subgraphs. We present bounds for the VC-dimension of a graph with respect to k-connected subgraphs and we study the computational complexity of the related decision problem.
  
  
• Jeudi 30 mai 2013 (à 14h30): Sylvia Boyd (Université d'Ottawa, Canada) : Theoretical and Experimental Studies on 2EC for Cubic Bridgeles Graphs
  
  Given an unweighted bridgeless graph G with n vertices, the minimum size 2-edge-connected subgraph problem, denoted by 2EC, is the problem of finding a 2-edge-connected subgraph of G with the minimum number of edges. This problem is known to be NP-hard, even for cubic graphs.
  
  In this talk, we consider 2EC for cubic bridgeless graphs, and study the integrality gap alpha_2EC for these graphs, which is the worst-case ratio between the optimal solution value for 2EC and the linear programming relaxation solution for this problem. It has been conjectured that alpha_2EC = 6/5. Currently it is known that 9/8 <= alpha_2EC <= 5/4 + epsilon. We improve upon both this upper bound and lower bound, and provide a new 5/4-approximation algorithm for this problem. We also find the exact value of alpha_2EC for graphs with small n through a computational study.
  
  Joint work with Yu Sun.
  
  
• Vendredi 24 mai 2013 (à 15h): Roland Grappe (LIPN, Paris Nord) : Reverse Chvatal-Gomory Rank
  
  We introduce the reverse Chvatal-Gomory rank r*(P) of an integral polyhedron P, defined as the supremum of the Chvatal-Gomory ranks of all rational polyhedra whose integer hull is P. A well-known example in dimension two shows that there exist integral polytopes P with r*(P) infinite. We provide a geometric characterization of polyhedra with this property in general dimension, and investigate upper bounds on r*(P) when this value is finite.
  
  Joint work with Michele Conforti, Alberto Del Pia, Marco Di Summa and Yuri Faenza.
  
  
• Jeudi 23 mai 2013 (à 14h30): Stanislas Francfort (Orange) : Problèmes d'optimisation dans le déploiement de la fibre optique
  
  Dans le contexte du renouvellement des réseaux pour la montée en débit, plusieurs milliards d'euros d'investissement sont prévus. Afin d'optimiser les coûts de déploiement et de maintenance, France Télécom met en oeuvre un outil automatisé d'aide à la décision et d'optimisation. Les problèmes que doit résoudre cet outil sont de diverses natures : design de réseau (localisation/routage), regroupement (clustering), affichage...
  Lors de cet exposé, je vous présenterai ces problèmes, leurs enjeux, ainsi que les questions que nous souhaiterions savoir résoudre.
  
  
• Jeudi 16 mai 2013 (à 14h30): Gautier Stauffer (G-SCOP) : When Fourier-Motzin meets shortest paths (on the way to clique covers in claw-free perfect graphs)
  
  We give new algorithms for the minimum (weighted) clique cover in a claw-free perfect graph $G$, improving the complexity from $O(|V(G)|^5)$ to $O(|V(G)|^3)$. The new algorithms build upon neat reformulations of the problem: it basically reduces either to solving a 2-SAT instance (in the unweighted case) or to testing if a polyhedra associated with the edge-vertex incidence matrix of a bidirected graph has an integer solution (in the weighted case). The latter question was elegantly answered using neat polyhedral arguments by Schrijver in 1994. We give an alternative approach to this question combining pure combinatorial arguments (using techniques from 2-SAT and shortest paths) with polyhedral ones.
  
  Our approach is inspired by an algorithm from the Constraint Logic Programming community and we give as a side benefit a formal proof that the corresponding algorithm is correct (apparently answering an open question in this community). Interestingly, the systems we study have properties closely connected with the so-called Edmonds-Johnson property and we study some interesting related questions.
  
  
• Jeudi 18 avril 2013 (à 14h30): Vincent Jost (LIX, Palaiseau) : Shortest spanning closed walk in interval graphs and vertex minors
  
  A shortest spanning closed walk (SSCW) is both a generalization of a Hamiltonian cycle and a special case of a shortest travelling salesman tour (TSP). We want to find a cycle in the input graph, going through each vertex at least once, minimizing the (weighted) number of transit occurrences through vertices (while travelling on edges is free).
  
  This problem can be thought of a TSP on specific metrics. We will mention related problems on graphs which can be thought of as TSP with specific metrics and are known to be polynomial on the same classes of graphs.
  
  The non-weighted version of SSCW is polynomial and admits a min-max formula on interval graphs. The min-max formula and polynomiality are conjectured to extend to the weighted case, but also to substantially larger classes of graphs (co-comparability, AT-free...). An advantage of min-max formulas over algorithms is that they help tracking polynomial solvable problems, sometimes without any idea of the algorithm required to solve the problem.
  
  Based on joint work with Guyslain Naves, LIF, Marseille.
  
  
• Mercredi 3 avril 2013 (à 16h): Tim Nonner (IBM Research, Zurich) : An Efficient Polynomial-Time Approximation Scheme for the Joint Replenishment Problem
  
  We give an efficient polynomial-time approximation scheme (EPTAS) for the Joint Replenishment Problem (JRP) with stationary demand. Moreover, using a similar technique, we give a PTAS for the capacitated JRP with non-stationary demand but constant size capacities.
  
  Joint work with Maxim Sviridenko.
  
  
• Lundi 18 mars 2013 (à 15h): Marco Laumanns (IBM Research, Zurich) : Multi-Period Production Planning Under Non-Compliance Risk
  
  This talk addresses a production planning setting for pharmaceutical companies under the risk of failing quality inspections undertaken by the regulatory authorities. After reviewing the single-period problem of maximizing the worst-case revenue and the worst-case expectation, different stochastic programming and dynamic programming formulations for the multi-period version are discussed. We show how decision-dependent probabilities, which are due to risk transfer between products of the same site, can be handled by solving a MINLP for each state in the multi-period dynamic program.
  
  Joint work with Alwin Haensel, Ban Kawas, Eleni Pratsini, Steven Prestwich and Catalin-Stefan Tiseanu.
  
  
• Jeudi 14 février 2013 (à 14h30): Alantha Newman (EPFL, Lausanne) : Beck's Three Permutations Conjecture: A Counterexample and Some Consequences
  
  Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. In 1982, Beck conjectured that the discrepancy of this set system is O(1). In other words, the conjecture says that each integer from 1 through n can be colored either red or blue so that the number of red and blue integers in each interval of each permutations differs only by a constant. (The discrepancy of a set system based on two permutations is at most two.)
  
  We will present a counterexample to this conjecture: for any positive integer n = 3^k, we construct three permutations whose corresponding set system has discrepancy Omega(log(n)).
  
  Our work was inspired by an intriguing paper from SODA 2011 by Eisenbrand, Palvolgyi and Rothvoss, who show a surprising connection between the discrepancy of three permutations and the bin packing problem: They show that Beck's conjecture implies a constant worst-case bound on the additive integrality gap for the Gilmore-Gomory LP relaxation for bin packing in the special case when all items have sizes strictly between 1/4 and 1/2, also known as the three partition problem. Our counterexample shows that this approach to bounding the additive integrality gap for bin packing will not work. We can, however, prove an interesting implication of our construction in the reverse direction: there are instances of bin packing and corresponding optimal basic feasible solutions for the Gilmore-Gomory LP relaxation such that any packing that contains only patterns from the support of these solutions requires at least OPT + Omega(log(m)) bins, where m is the number of items.
  
  Joint work with Ofer Neiman and Aleksandar Nikolov.
  
  
• Jeudi 31 janvier 2013 (à 14h30): Yves Crama (Université de Liège, Belgique) : Algorithmes d'approximation pour les problèmes d'affectation multidimensionnels
  
  Le problème d'affectation multidimensionnel (PAM) consiste à partitionner les sommets d'un graphe m-parti en m-cliques disjointes de façon à minimiser la somme des coûts des cliques utilisées, où le coût des cliques peut être défini de différentes façons. PAM généralise le problème d'affectation ou de couplage biparti classique qui correspond au cas m=2.
  
  Nous présentons plusieurs résultats, anciens et nouveaux, relatifs à des cas particuliers de PAM obtenus en spécifiant les propriétés du coût des cliques. Pour ces cas particuliers, nous décrivons des algorithmes d'approximation, nous examinons leurs garanties de performanc, et nous mentionnons quelques questions ouvertes.
  
  
• Jeudi 24 janvier 2013 (à 14h30): Olivier Durand de Gevigney (G-SCOP, Grenoble) : Orientation des Graphes et Connexité
  
  Nous étudions les graphes qui admettent une orientation satisfaisant certaines propriétés de connexité. Nash-Williams a prouvé que les graphes qui admettent une orientation k-arc-connexe sont les graphes 2k-arête-connexes. Frank a conjecturé en 1995 que les graphes qui admettent une orientation k-sommet-connexe sont les graphes faiblement 2k-connexes. Nous donnons un contre-exemple à cette conjecture et montrons que décider si un graphe a une orientation k-sommet-connexe est NP-complet. Nous montrons ensuite comment ces résultats s'étendent à la "racine sommet-connexité".
  
  
• Jeudi 13 décembre 2012 (à 14h30): Denis Cornaz (LAMSADE, Paris Dauphine) : Extension du théorème de Konig aux graphes non-bipartis
  
  Un énoncé équivalent au théorèm de Konig (qui dit qu'on peut colorier de manière propre les arêtes des graphes bipartis de degré max D avec D couleurs) est un système TDI minimal décrivant le polytope des étoiles des graphes bipartis (les étoiles peuvent avoir des arêtes multiples). Une autre conséquence de ce théorème, mais moins forte que le théorème lui-même, est un système TDI non-minimal décrivant le polytope des étoiles de tout graphe. Donc la minimalité d'un système TDI est intéressante.
  Nous donnons un système TDI minimal décrivant le polytope des étoiles de tout graphe et qui est plus fort que le théorème de Konig.
  Pour expliquer la relation min-max derrière on définit un ocm = l'ensemble des arêtes de l'union-disjointe d'un couplage et de plusieurs circuits impairs (ocm pour odd-cycle, matching). Remarquons que tout ocm est un 2-matching mais pas l'inverse: les 2-matchings ayant des cycles pairs et des chemins peuvent être des combinaisons non-entière d'ocm's. Une couverture ocm est formée d'ocm's tels que chaque arête appartient au couplage d'au-moins un ocm ou à un circuit impair d'au moins deux ocm's. Le degré maximum est égal au nombre minimum d'ocm's dans une couverture ocm.
  
  Travail en commun avec V.H. Nguyen (LIP6, Université Pierre et Marie Curie)
  
  
• Jeudi 29 novembre 2012 (à 14h30): Andras Sebo (G-SCOP, Grenoble) : (8/5)-approximation des chemins du Voyageur de Commerce
  
  Un Voyageur de Commerce doit passer dans certaines villes pour son travail. Il part de son domicile, fait ses visites, et comme c'est vendredi, il veut finir dans sa résidence de campagne. Nous montrons quelques idées et une amélioration de la garantie d'approximation pour ce problème. La place du nouveau résultat parmi ses prédécesseurs peut être comprise en terme de nombres de Fibonacci:
  
  Une partie de la suite de Fibonacci : 2, 3, 5, 8, 13
  On sait que les quotients a_{i+1} / a_i convergent vers le nombre d'or, et lui sont alternativement inférieurs et supérieurs.
  
  3/2 : c'est la conjecture pour la meilleure garantie d'approximation.
  5/3 : c'est la garantie de l'adaptation de l'algorithme et de l'analyse de Christofides que l'on peut facilement montrer.
  Le nombre d'or : la garantie d'approximation de An, Kleinberg et Shmoys (2012).
  13/8 : la garantie d'approximation pour une généralisation aux T-joins de Cheriyan, Friggstad et Gao (2012)
  8/5 : la nouvelle garantie d'approximation que je vais présenter lors de cet exposé.
  
  
• Jeudi 22 novembre 2012 (à 14h30): Viet Hang Nguyen (G-SCOP, Grenoble) : On universally rigid frameworks on the line
  
  One approach to the problem of sensor network localization is to use semidefinite programming (SDP). However, even in the case that the position of nodes in the network is unique subject to avalaible distance measurements in the considered dimension, SDP can give a solution in higher dimension (unfortunately, it is always the case if such a solution exists).
  
  The class of networks for which SDP works accurately (and so efficiently) is that of universally rigid networks. The class of underlying graphs so that every "generic" network is universally rigid is also of interest. They are called generically universally rigid graphs.
  
  Although other more classic types of rigidity such as local rigidity and global rigidity is well studied and especially well understood in dimension 2, little is known about universal rigidity even in dimension 1. In our work we give a complete characterization of the universal rigidity of complete bipartite networks in dimension 1. The proof then can be used to show that complete bipartite graphs are not generically universally rigid in any dimension. We also discuss several open questions concerning generically universally rigid graphs and the universal rigidity of general networks on the line.
  
  Joint work with Tibor Jordan at Eotvos Lorand University, Budapest
  
  
• Jeudi 25 octobre 2012 (à 11h): Frédéric Meunier (CERMICS, ENPC, Marne-la-Vallée) : Un cadre combinatoire pour la profondeur simpliciale colorée
  
  Le théorème de Carathéodory coloré, dû à Bárány, affirme que si l'on se donne d+1 ensembles de points S_1,...,S_{d+1} dans R^d, chacun d'eux contenant l'origine dans son enveloppe convexe, alors il est possible de choisir un point p_i dans chaque S_i et d'avoir encore l'origine dans l'enveloppe convexe des p_i. L'enveloppe convexe des p_i est alors appelée "simplexe coloré contenant l'origine". Le nombre de simplexes colorés contenant l'origine est la "profondeur simpliciale colorée" de l'origine.
  Une question qui a reçu une attention particulière est celle de savoir quelle est la plus petite profondeur simpliciale colorée possible dans le cas où chaque S_i est de cardinalité d+1. Le théorème de Bárány montre qu'elle vaut au moins 1. La valeur minimale mu(d) qu'elle peut prendre a été étudiée par Deza et al., Bárány et Matousek, et Stephen et Thomas, qui ont montré que mu(d) vaut toujours au moins (d^2+2d+1)/2 et au plus d^2+1. La conjecture que mu(d) vaut d^2+1 a été vérifiée en dimensions 1,2 et 3.
  Dans cet exposé, nous améliorons la borne inférieure et montrons que mu(d) vaut toujours au moins (d^2+7d-14)/2. Nous montrons également que mu(4)=17, et donc que la conjecture est vraie en dimension 4. Les preuves utilisent des hypergraphes particuliers spécialement conçus pour ce problème - les systèmes octaédriques, dont l'étude a été récemment suggérée par Bárány. Quelques résultats théoriques les concernant seront également présentés.
  
  Résultats obtenus par un travail commun avec Antoine Deza (McMaster University) et Pauline Sarrabezolles (Ecole des Ponts).
  
  
• Jeudi 18 octobre 2012 (à 14h): Nicolas Catusse (G-SCOP, Grenoble) : Réseaux de Manhattan dans le plan normé et réseaux de Manhattan orientés
  
  Pour un ensemble de terminaux T dans le plan, un réseau de Manhattan est un réseau dans lequel il existe un plus court chemin rectilinéaire entre chaque paires de terminaux. Un réseau de Manhattan minimal est un réseau de Manhattan de longueur minimale. Nous commençons par étudier la généralisation du problème du réseau de Manhattan classique aux plans normés dont la boule unitaire est un polygone convexe central symétrique. Étant donné un ensemble de terminaux, nous recherchons le réseau de longueur totale minimum qui connecte chaque paire de terminaux par un plus court chemin dans la métrique définie par la norme. Nous proposons un algorithme d'approximation facteur 2.5 pour ce problème en temps O(mn^3) avec n le nombre de terminaux et m le nombre de directions de la boule unitaire. Le deuxième problème étudié est une version orientée des réseaux de Manhattan dont le but est de construire un réseau orienté de taille minimum dans lequel pour chaque paire de terminaux u, v est relié par un plus court chemin rectilinéaire de u vers v et un autre de v vers u. Nous proposons un algorithme d'approximation facteur 2 pour ce problème en temps O(n^3) où n est le nombre de terminaux.
  
  Travail effectué en collaboration avec Victor Chepoi, Karim Nouioua et Yann Vaxès
  
  
• Jeudi 11 octobre 2012 (à 14h30): Egor Gladkikh (G-SCOP, Grenoble) : Configuration optimale des réseaux de distribution de l'énergie électrique
  
  Je vais présenter le sujet de ma thèse, issu d'une problématique industrielle. Le réseau en question peut être défini comme un graphe planaire où un noeud particulier représente une centrale et les autres les consommateurs. Le graphe du réseau électrique est non orienté et contient des cycles mais la distribution doit être réalisée dans une arborescence (graphe orienté) ayant la centrale comme racine. L'acheminement de l'énergie doit être réalisé en minimisant les pertes Joules (dissipation d'énergie électrique sous forme de chaleur : P=RI^2) en respectant les limites du courant sur les branches utilisées. Le modèle physique exact, couramment utilisé, est extrêmement difficile - l'objectif et les contraintes sont non-linéaires. Je propose quelques pistes pour étudier un problème relaxé. Puisque les réseaux électriques obéissent à la loi de Kirchhoff, on peut considérer ce problème comme la recherche du flot de coût quadratique minimum. La recherche d'une r-arborescence peut être réalisée par la programmation linéaire où considérée comme l'intersection de deux matroïdes. Les difficultés sont liées à l'objectif quadratique et les limitations des capacités des arcs.
  
  
• Jeudi 4 octobre 2012 (à 14h30): Francis Lazarus (GIPSA-Lab, Grenoble) : Sur le test d'homotopie entre courbes tracées sur une surface
  
  Étant donnée deux courbes tracées sur une surface combinatoire, le test d'homotopie consiste à décider si ces courbes peuvent se déformer continûment l'une en l'autre sur la surface. Je décrirai comment répondre à ce test en temps optimal, proportionnel à la taille de la surface et des courbes données.
  
  
• Jeudi 27 septembre 2012 (à 14h30): Louis Esperet (G-SCOP, Grenoble) : Couverture et packing de boules dans les graphes planaires
  
  Chepoi a conjecturé l'existence d'une constante c telle que pour tout graphe planaire G et pour tout entier R, soit il existe k+1 sommets 2 à 2 à distance au moins 2R+1, soit il existe un ensemble S d'au plus c*k sommets tel que chaque sommet de G est à distance au plus R d'un sommet de S. En d'autres termes, la taille min d'un transversal des boules de rayon R est au plus c fois la taille max d'un packing de boules de rayon R (et c ne dépend pas de R!).
  J'expliquerai comment montrer une version plus faible de cette conjecture, où la constante c dépend de R. Le résultat s'étend à toute surface fixée. Dans le cas où R=1, le résultat est même valable pour toute classe (propre) de graphes close par mineurs.
  
  Travail en commun avec P. Charbit, J.-S. Sereni, et Z. Yilma.
  
  
• Jeudi 6 septembre 2012 (à 14h30): Tomas Kaiser (Université de Plzen, République Tchèque) : The toughness of graphs
  
  A graph G is t-tough if the removal of any set X of vertices leaves a graph with at most |X|/t components. Chvatal conjectured long ago that there is a constant k such that every k-tough graph is hamiltonian. We discuss several problems and results related to this conjecture.