Séminaires 2018 - 2019

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.

Il y aura moins de séminaires que d'habitude au premier semestre, en raison de la mise en place d'un groupe de lecture sur la théorie algorithmique des jeux les jeudis après-midi à l'occasion de la remise du prix Jean Kuntzmann 2019 à Eva Tardos.

• Jeudi 18 juillet 2019 (à 14h30): Louis Esperet (G-SCOP) : Algorithmes distribués en optmisation combinatoire
  
  Dans cet exposé je présenterai les idées de bases permettant de résoudre des problèmes classiques d'optimisation combinatoire (Coloration, Couplage) dans le cadre de l'algorithme distribuée. Il n'y a pas de prérequis sur le calcul distribué, j'expliquerai tout ce qui est nécessaire. Je montrerai aussi comment prouver des bornes inférieures en utilisant des résultats de complexité de communication. Si le temps le permet je mentionnerai quelques résultats obtenus récemment sur des problèmes liés (notamment en collaboration avec E. Bamas).
  
  
  
• Jeudi 20 juin 2019 (à 14h30): Claude Lemaréchal (Retraité INRIA) : Quelques problèmes combinatoires dans l'organisation des compétitions de bridge
  
  Au bridge, une compétition réunissant un grand nombre de joueurs nécessite souvent une organisation entraînant des problèmes combinatoires non triviaux. Dans ces notes, on évoque deux problèmes concernant les compétitions par équipe, c'est-à-dire consistant en un certain nombre de duels entre n équipes (n>2). L'un, assez général, concerne les poules où n est trop grand pour permettre de jouer tous les duels. Sélectionner un sous-ensemble convenablement significatif conduit à un problème d'optimisation (combinatoire) bien défini. Pour l'autre, la question est de jouer les duels simultanément lorsque n est impair. Paradoxalement, c'est possible, grâce à une particularité unique des matches de bridge. Cela mène plutôt à des questions théoriques de couplages imbriqués.
  
  
  
• Mardi 11 juin 2019 (à 10h, en salle H201): Rico Zenclusen (ETH Zürich) : A 1.5-Approximation for Path TSP
  
  I will present a 1.5-approximation for the Metric Path Traveling Salesman Problem (path TSP). All recent improvements on path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that cuts with a value strictly below 2 with respect to any Held-Karp solution form a chain. Such narrow cuts are the obstacle why Christofides' celebrated 1.5-approximation for TSP does not easily extend to the more general path version of TSP. The approach I introduce significantly deviates from prior techniques in this point, by showing the benefit of not only focussing on narrow cuts, but instead dealing with larger s-t cuts even though they are much less structured. More precisely, we will see that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. Through this technique, we obtain a well-structured point in the Held-Karp relaxation from which we derive the 1.5-approximation. This allows us to avoid a recursive application of dynamic programming as used by Traub and Vygen in their recent (1+epsilon)-approximation, and we obtain a considerably simpler algorithm avoiding an additional error term in the approximation guarantee. The obtained approach matches the still unbeaten 1.5-approximation guarantee of Christofides' algorithm for TSP. Hence, any further progress on the approximability of path TSP will also lead to an improvement over Christofides' 1.5-approximation for TSP.
  
  
  
• Jeudi 16 mai 2019 (à 14h30): Chien-Chung Huang (ENS Ulm, Paris) : Popularity, Mixed Matchings, and Self-duality
  
  We consider the problem of matching applicants to jobs under two-sided preferences in a popular and utility-optimal manner. Our input instance is a bipartite graph G = (A \cup B,E) with a utility function w: E \rightarrow Q where each vertex u \in A \cup B has a preference list ranking its neighbors in a strict order of preference. For any two matchings M and T in G, let \phi(M,T) be the number of vertices that prefer M to T. A matching M is popular if \phi(M,T) \geg \phi(T,M) for all matchings T in G. A mixed matching is defined as \Pi = \{(M_0,p_0),\ldots,(M_k,p_k)\} for some matchings M_0,\ldots,M_k and \sum_{i=0}^kp_i = 1, p_i \geq 0 for all i. The function \phi(\cdot,\cdot$ easily extends to mixed matchings; a mixed matching \Pi is popular if \phi(\Pi,\Lambda) \geq \phi(\Lambda,\Pi) for all mixed matchings \Lambda in G.
  
  Motivated by the fact that a popular mixed matching could have a much higher utility than all popular matchings, we study the popular fractional matching polytope {\cal P}_G. Our main result is that this polytope is half-integral (and in the special case where a stable matching is a perfect matching, this polytope is integral), implying that there is always a max-utility popular mixed matching \Pi such that \Pi = {(M_0,\frac{1}{2}),(M_1,\frac{1}{2})} and \Pi can be computed in polynomial time. An immediate consequence is that in order to implement a max-utility popular mixed matching in G, we need just one single random bit.
  
  We analyze {\cal P}_G whose description may have exponentially many constraints via an extended formulation in m+n dimensions with O(m+n) constraints. The linear program that gives rise to this formulation has an unusual property: self-duality. In other words, this linear program is exactly identical to its dual program. This is a rare case where an LP of a natural problem has such a property. The self-duality of the LP plays a crucial role in our proof of the half-integrality of {\cal P}_G.
  
  We also show that our result carries over to the roommates problem, where the given graph G may not be bipartite. The polytope of popular fractional matchings is still half-integral here and thus we can compute a max-utility popular half-integral matching in G in polynomial time. To complement this result, we also show that the problem of computing a max-utility popular (integral) matching in a roommates instance G is NP-hard.
  
  
  
• Jeudi 9 mai 2019 (à 14h30): Ioannis Panagiotas (LIP, ENS de Lyon) : Approximate Algorithm for Maximum Matching In Undirected Graphs
  
  We propose heuristics for approximating the maximum cardinality matching on undirected graphs. Our heuristics are based on the theoretical body of a certain type of random graphs, and are made practical for real-life ones. The idea is based on judiciously selecting a subgraph of a given graph and obtaining a maximum cardinality matching on this subgraph. We show that the heuristics have an approximation guarantee of around 0.866 - log(n)/n for a graph with n vertices. Experiments for verifying the theoretical results in practice are provided.
  
  
  
• Jeudi 2 mai 2019 (à 14h30): Mikaël Rabie (IRIF, Paris) : Lower bounds for maximal matchings and maximal independent sets
  
  There are distributed graph algorithms for finding maximal matchings and maximal independent sets in O(Delta+log^*n) communication rounds; here n is the number of nodes and Delta is the maximum degree. The lower bound by Linial (1987, 1992) shows that the dependency on n is optimal: these problems cannot be solved in o(log^*n) rounds even if Delta=2. However, the dependency on Delta is a long-standing open question, and there is currently an exponential gap between the upper and lower bounds.
  We prove that the upper bounds are tight. We show that maximal matchings and maximal independent sets cannot be found in o(Delta+log log n/log log log n) rounds with any randomized algorithm in the LOCAL model of distributed computing. As a corollary, it follows that there is no deterministic algorithm for maximal matchings or maximal independent sets that runs in o(Delta+log n/log log n) rounds; this is an improvement over prior lower bounds also as a function of n.
  
  This is a joint work with Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti and Jukka Suomela.
  
  
  
• Jeudi 11 mars 2019 (à 14h30): Frédéric Meunier (CERMICS) : Optimiser les « rotations équipages » d'une compagnie aérienne
  
  Le personnel est l'une des sources principales des coûts d'exploitation d'une compagnie aérienne. Optimiser l'affectation des équipages aux vols est donc crucial pour la rentabilité d'une telle entreprise. Cette affectation consiste à trouver une couverture optimale des sommets du "graphe des vols" par des chemins élémentaires. Ces chemins forment alors le planning des équipages et sont appelés rotations équipages. Chacune de ces rotations doit satisfaire un grand nombre de contraintes induites par la réglementation et les conventions collectives.
  Ce problème est d'une complexité redoutable car, d'une part, l'espace des solutions est gigantesque et, d'autre part, les contraintes mentionnées ci-dessus sont difficiles à modéliser mathématiquement. Nous démontrons cependant que ces contraintes peuvent être munies d'une structure de treillis, ce qui permet l'utilisation d'algorithmes de plus courts chemins s'appuyant sur des bornes et des propriétés de dominance. L'approche usuelle par génération de colonnes passe alors à l'échelle : nous résolvons à l'optimalité les instances réelles d'Air France, qui peuvent mettre en jeu des réseaux de l'ordre de 3000 vols sur une semaine.
  Enfin, nous montrons également comment il est possible d'optimiser simultanément les itinéraires des avions sur le même graphe des vols, ce qui permet, en raison de certaines contraintes techniques liantes, une réduction additionnelle des coûts.
  
  Travail joint avec Axel Parmentier.
  
  
  
• Jeudi 14 mars 2019 (à 14h30): Julien Baste (Universität Ulm) : Hitting minors on bounded treewidth graphs
  
  For a fixed collection of graphs F, the F-DELETION problem consists in, given a graph G and an integer k, decide whether there exists S, subset of V(G), with |S| <= k such that G-S does not contain any of the graphs in F as a minor. This NP-hard problem is a generalization of some well known graph problems as VERTEX COVER (F={K_2}), FEEDBACK VERTEX SET (F={K_3}), or VERTEX PLANARIZATION (F={K_5,K_{3,3}}). We are interested in its parameterized complexity when the parameter is the treewidth of G, denoted by tw. Namely, the objective is to determine, for a fixed F, the (asymptotically) smallest function f_F: N -> N such that F-DELETION can be solved in time f_F(tw)*n^{O(1)} on n-vertex graphs. In this talk we will provide the basic definitions of parameterized complexity, motivate the problem, and then, review some of the lower and upper bounds on the function f_F for several instantiations of F.
  
  The presented results are joint work with Ignasi Sau and Dimitrios Thilikos and can be found here.
  
  
  
• Jeudi 7 mars 2019 (à 14h30): François Dross (I3S, Sophia-Antipolis) : Trees in tournaments
  
  A tournament is an orientation of a complete graph. A digraph D is said to be k-unavoidable if it is contained in every tournament of order k. As the transitive tournament of order n is (2^(n-1))-unavoidable, every graph of order n is (2^(n-1))-unavoidable. However, for some particular digraphs one can obtain a better bound.
  In this presentation we will focus on orientations of trees. Sumner conjectured that every tree of order n > 1 is (2n-2)-unavoidable, and Havet and Thomassé made the strengthened conjecture that every tree of order n > 1 with k leaves is (n+k-1)-unavoidable. We will see some techniques to approach these conjectures.
  
  
  
• Mardi 19 février 2019 (à 14h30, au LIG): David Shmoys (Cornell University) : Algorithms for the Operation and Design of Bike-sharing Systems
  
  Bike-sharing systems are changing the urban transportation landscape; for example, New York launched the largest bike-sharing system in North America in May 2013, and by 2017 there were roughly 17 million individual trips taken. We have worked with Citibike and their parent company Motivate, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system - we answer the following two questions: where should bikes be at the start of a day and how can we mitigate the imbalances that develop? We will survey the algorithmic tools we have employed for the former question, where we developed an approach based on continuous-time Markov chains combined with integer programming models to compute stocking levels for the bikes, as well as methods employed for optimizing (and re-optimizing) the capacity of the stations. For the question of mitigating the imbalances that result, we will describe both heuristic methods and approximation algorithms that guide both mid-rush hour and overnight rebalancing, as well as for the positioning of corrals, which have been one of the most effective means of creating adaptive capacity in the system. More recently, we have guided the development of Bike Angels, a program to incentivize users to crowdsource "rebalancing rides", and we will describe its underlying analytics.
  
  This is joint work with Daniel Freund, Shane Henderson, and Eoin O'Mahony, as well as Hangil Chung, Aaron Ferber, Nanjing Jian, Ashkan Nourozi-Fard, Alice Paul, and David Williamson.
  
  
  
• Jeudi 24 janvier 2019 (à 14h30): Andrei Raigorodskii (MIPT, Moscou) : The independence numbers and the chromatic numbers of random subgraphs in some sequences of graphs
  
  tba
  
  
  
• Jeudi 22 novembre 2018 (à 14h30): Jean-Florent Raymond (TU Berlin) : Énumérer les dominants dans les graphes sans triangle
  
  Étant donné un graphe, peut-on efficacement lister tous ses ensembles dominants minimaux ? Comme ceux-ci peuvent être en nombre exponentiel (en la taille du graphe), on cherche ici un algorithme dont le temps d'exécution est borné polynomialement en fonction de la taille du résultat (en non en fonction de la taille de l'entrée comme habituellement). L'existence d'un algorithme efficace pour énumérer les dominants minimaux est un problème ouvert depuis plusieurs décennies et a des liens avec de nombreux autres problèmes d'autres domaines. Dans cet exposé, je présenterai un algorithme efficace dans les graphes sans triangle, ce qui répond à une question de Kanté et al.
  
  Travail commun avec Marthe Bonamy, Oscar Defrain et Marc Heinrich.
  lien vers l'article
  
  
  
• Mardi 9 octobre 2018 (à 11h): Tom Kelly (Université de Waterloo) : On the density of critical graphs without large cliques
  
  A graph is k-critical if it has chromatic number k and every proper subgraph is (k - 1)-colorable. The density of critical graphs has been extensively studied. We present an improvement on the best known lower bound for the density of critical graphs without large cliques. We also discuss a connection to list-coloring and generalizations of Reed's Conjecture.
  
  Joint work with Luke Postle.