*   Domaine de compétence Optimisation Combinatoire   *
  *    Séminaire
  o    2018 - 2019
  o    2017 - 2018
  o    2016 - 2017
  o    2015 - 2016
  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 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.

11 avril 2019 Frédéric Meunier
(CERMICS)
Optimiser les « rotations équipages » d'une compagnie aérienne
14 mars 2019 Julien Baste
(Universität Ulm)
Hitting minors on bounded treewidth graphs
7 mars 2019 François Dross
(I3S, Sophia-Antipolis)
Trees in tournaments
19 février 2019 David Shmoys
(Cornell University)
Algorithms for the Operation and Design of Bike-sharing Systems
24 janvier 2019 Andrei Raigorodskii
(MIPT, Moscou)
The independence numbers and the chromatic numbers of random subgraphs in some sequences of graphs
22 novembre 2018 Jean-Florent Raymond
(TU Berlin)
Énumérer les dominants dans les graphes sans triangle
9 octobre 2018 Tom Kelly
(Université de Waterloo)
On the density of critical graphs without large cliques
  • 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.