Programme du séminaire "optimisation discrète"
• 15/11/07 (salle 3.23) : Gérard Cornuéjols
: "Approche polyèdrale pour la programmation en nombres entiers"
Cet exposé présente une théorie des inégalités
valides en programmation en nombres entiers. On donne une interprétation
géométrique de plusieurs familles d'inégalités
valides telles que les coupes "lift-and-project", les coupes mixtes
de Gomory, les coupes "split" et les coupes par "intersection",
et on révèle les relations entre ces familles. On mentionne également
les aspects numériques de la génération de ces coupes
et leur force.
Transparents de la présentation : ICI
• 29/11/07 (salle 1.4) : Patrice Ossona de
Mendez : "Partitions régulières de graphes épars
et applications"
Le grad de rang r d'un graphe G est la densité maximale d'un mineur
de G obtenu en contractant un ensemble de sous graphes sommets-disjoints de
rayons au plus r, en simplifiant le graphe et en effaçant arbitrairement
des sommets et des arêtes. Une classe de graphe C est d'expansion
bornée si supG∈C ∇r(G)<∞ (pour tout entier r). Ainsi, toute classe
propre fermée par mineur, toute classe de degré borné,
mais aussi toute classe composée de squelettes de complexes simpliciaux
de dimension d et d'aspect ratio borné et, plus généralement,
toute classe excluant un mineur topologique sont des classes d'expansion bornée.
Le tree-depth td(G) d'un graphe G est la hauteur minimale d'une forêt enracinée dont la fermeture inclue G. Pour toute classe C d'expansion bornée et pour tout entier p, il existe une constante N(C,p) telle que tout graphe G∈C possède une partition de ses sommets en au plus N(C,p) parties telle que i≤p parties induisent un sous graphe de tree-depth au plus i. De plus, une telle partition peut être calculée en temps linéaire par un algorithme simple.
Le calcul d'une telle partition permet alors d'obtenir de nombreux algorithmes en temps linéaires (pour des graphes appartenant à une classe d'expansion bornée). En particulier : la recherche et de dénombre des sous graphes isomorphes à un sous graphe fixé, la vérification d'une propriété du premier ordre fixée, l'énumération des ensembles dominants de taille au plus k (fixé).
Transparents de la présentation : ICI
• 20/12/07 (salle 3.23) : Éric Sopena
: "Sommet
et Arc-Coloration des Graphes Orientés"
Nous considérons des graphes orientés antisymétriques
(sans boucles ni arcs opposés), simplement désignés par
le terme "graphes
orientés". Une k-sommet-coloration d'un graphe orienté G est
une partition de l'ensemble des sommets de G en k sous-ensembles
de façon telle que tous les arcs
reliant un sous-ensemble à un autre ont même direction. Une telle
coloration peut être vue, de façon équivalente,
comme un homomorphisme de G vers un graphe orienté à k sommets.
Les colorations orientées ont été étudiées par plusieurs personnes depuis une quinzaine d'années. Dans cet exposé, après avoir introduit les quelques notions de base qui nous sont nécessaires, nous présenterons les principaux résultats de ce domaine, en illustrant les différentes techniques utilisées pour les obtenir.
Nous nous intéresserons également à la notion d'arc-coloration, qui découle naturellement de la notion de sommet-coloration (une arc-coloration d'un graphe orienté étant simplement une sommet-coloration de son graphe représentatif des arcs).
Nous mentionnerons enfin plusieurs questions ouvertes qui nous tiennent particulièrement à coeur.
Transparents de la présentation : ICI
• 17/01/08 (salle 3.23) : Frédéric Havet : "Méthode de Déchargement".
La Méthode de Déchargement a été développée afin de montrer le célèbre théorème des 4 couleurs. Depuis une quinzaine d'années, cette méthode a été utilisée pour résoudre de nombreux problèmes en particulier sur les graphes planaires et les graphes de densité (degré moyen maximum) bornée.
Dans cette exposé, nous expliquerons les principes de la Méthode de Déchargement et l'illustrerons par quelques exemples de coloration de graphes.
Notes de la présentation : ICI
Résumé de la présentation : ICI
Transparents de la présentation : ICI
• 14/02/08 (salle 3.23) : Victor Chepoï : "Conception des algorithmes d'approximation par arrondi"
We will present the basic rounding techniques for designing approximation algorithms. In the first part of the talk, we will recall and analyze the rounding algorithms for Vertex Cover, Set Cover, MAX-SAT and Steiner Network problems. In the second part of the talk, we will present a rounding factor 2 approximation algorithm for solving the minimum Manhattan network problem.
For a set T of n points (terminals) in the plane, a Manhattan network on T is a network N with the property that its edges are horizontal or vertical segments and for every pair of terminals, the network N contains a shortest Manhattan path between them. A minimum Manhattan network on T is a Manhattan network of minimum possible length. The problem of finding minimum Manhattan networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) and its complexity status is unknown. Several approximation algorithms (with factors 8,4, and 3) have been proposed before. We describe a rounding 2-approximation algorithm based on a LP-formulation of the minimum Manhattan network problem (joint work with K. Nouioua and Y. Vaxes).
Transparents de la présentation : ICI
En collaboration avec B. Leroy Beaulieu (EPFL) et G. Di Stefano (Université de l'Aquilla).
Etant donné un nombre k, le problème de coloration bornée consiste à partitionner les sommets d'un graphe en un nombre minimum d'ensembles stables de taille au maximum k. k est une constante ou une fonction du graphe de sorte que ce problème généralise la coloration usuelle qui correspond à k=n.
Ces problèmes sont motivés par divers modèles de chemin de fer ou de robotique. Ils s'expriment en termes de graphes de permutation et, dans une forme plus générale, soit pour des graphes de comparabilité, soit pour des graphes d'overlap.
Nous considérons plusieurs modèles on-line consistant à révéler l'instance (permutation, système d'intervalle, ...), soit dans un ordre spécifique, soit dans un ordre quelconque.
Pour le cas k=n (coloration classique), nous commençons par un rapide tour d'horizon des résultats connus sur la coloration on-line des graphes de comparabilité et quelques résultats nouveaux. Nous abordons ensuite le cas des graphes d'overlap.
Nous nous intéressons alors à la coloration bornée (pour k constant) on-line des graphes de permutation.
Transparents de la présentation : ICI
À la fin du dix-huitième siècle, Condorcet proposait
une méthode fondée sur des comparaisons par paire comme méthode
de vote. On peut résumer le résultat d’une telle méthode à l’aide
d’un tournoi T pondéré : les sommets de T sont
les candidats ; un arc existe de x vers y si une majorité de
votants préfère x à y ; un arc (x, y)
est pondéré par
le nombre de votants qui préfèrent x à y moins
le nombre de votants qui préfèrent y à x (en
cas d’ex æquo,
l’arc est orienté arbitrairement et est pondéré par
0). Mais, même en supposant les préférences des votants
transitives, le tournoi T n’est pas nécessairement
transitif : des circuits peuvent exister.
Pour pallier cet inconvénient, on peut chercher un ordre total obtenu
en inversant un ensemble d’arcs dont la somme des poids soit minimum.
Ce problème, connu sous le nom de problème de l’ordre
médian (d’autres appellations existent), est NP-difficile.
Dans cet exposé, nous décrivons une méthode arborescente
par séparation et évaluation permettant de déterminer
les ordres médians d’un tournoi pondéré quelconque.
Le principe de séparation consiste à construire les ordres
totaux possibles en considérant des sections commençantes
de plus en plus longues ; différents principes d’élagage
sont appliqués, résultant de propriétés combinatoires
des vainqueurs. La fonction d’évaluation est donnée
par la relaxation lagrangienne des contraintes de transitivité dans
l’expression du problème sous forme de programme linéaire
en 0-1. La borne initiale est calculée à l’aide d’une
métaheuristique, plus précisément à l’aide
d’une méthode de bruitage auto-réglé.
Le programme est disponible à l’adresse http://www.enst.fr/~charon/tournament/median.html.
Référence : Irène Charon, Olivier Hudry, « A branch and bound algorithm to solve the linear ordering problem for weighted tournaments », Discrete Applied Mathematics 154, 2097-2116, 2006.
Transparents de la présentation : ICI
La tomographie discrète consiste à reconstruire un objet à partir
d'un ensemble de ses projections. Il est couramment admis que le premier
problème de tomographie discrète, étudié par
H. Ryser à la fin des années 50 est la reconstruction d'une
matrice binaire.
La projection horizontale d'une matrice binaire est le vecteur H=(h1,...,hm)
où hi est la somme des éléments de la ligne i. De
façon analogue, la projection verticale est le vecteur V=(v1,...,vn)
où les sommes sont calculées par colonne.
La problématique est alors la suivante : étant données
les projections H et V :
- Existe-t-il une matrice binaire M ayant pour projections H et V ?
- Déterminer un algorithme "efficace" donnant M.
- La solution M est-elle unique ?
Ces questions ont été résolues par H. Ryser et des
algorithmes polynomiaux y répondent.
Ce problème a été généralisé de nombreuses manières : reconstruction d'une matrice colorée, reconstruction d'une matrice binaire avec contraintes (divers types de contraintes issues d'applications ont été introduites), reconstruction de pavage (par dominos, par polyominos, colorés ou monochromatiques), reconstruction d'empaquetages (ceci correspond à des problèmes d'ordonnancement), reconstruction de graphes,...
Du point de vue de la complexité beaucoup de ces généralisations conduisent à des problèmes NP-difficiles. Nous montrons un schéma de programmation dynamique applicable à la pluspart de ces problèmes. Ce schéma permet d'obtenir une complexité polynomiale lorsque l'une des deux dimensions de l'objet à reconstruire est de taille fixée.
• 29/05/08 (salle 2.23) : Zoltan Szigeti : "Une nouvelle caractérisation des graphes Seymour"
Un graphe G=(V,E) est dit Seymour si pour tout
sous-ensemble F des arêtes,
il existe |F| coupes disjointes contenant chacune un élément
de F, à condition que
chaque cycle contienne au moins autant d'arêtes appartenant à E-F qu'à F.
Cette condition est clairement nécessaire mais n'est en
général pas suffisante pour avoir un tel paquage de
coupes.
L'intérêt des graphes Seymour vient de leur connexion avec
le problème des chaînes disjointes dans les graphes planaires.
La définition ne met la propriété ni dans NP ni dans
co-NP. Nous allons présenter une caractérisation co-NP due à Ageev,
Kostochka, Szigeti (1997) puis une nouvelle caractérisation
co-NP due à Ageev, Sebö, Szigeti.
Transparents de la présentation : ICI
• 16/10/08 (salle 2.23) : Penny Haxell : "On the stable path problem"
The Border Gateway Protocol (BGP) is the interdomain routing protocol used to exchange routing information between Autonomous Systems (ASes) in the internet today. While intradomain routing protocols such as RIP are basically distributed algorithms for solving shortest path problems, the graph theoric problem that BGP as trying to solve is the stable paths problem (SPP). Unfortunately, unlike shortest path problems, it has been shown that instances of SPP can fail to have a solution and so BGP can fail to converge.
We define a fractional version of SPP and show that all instances of fractional SPP have solutions.
Transparents de la présentation : ICI
A first exercise in Graph Theory can easily be - in fact it is in Bollobás's Modern Graph Theory - that either the graph or its complement is connected. This remark of Erdös and Rado often considered as folklore - no wonder since its validity is obvious to anyone who understand the statement. An equivalent formulation is that in any 2-coloring of the edges of a complete graph, there is a monochromatic spanning tree. My aim is to survey results, problems and proof methods grown from this remark during the last forty years.
-type of spanning trees - height two trees, octopuses, brooms
-diameter - "small world", stars, double stars
-higher connectivity - finding a highly connected large piece
-Gallai colorings - an extension of 2-colorings
-many colors - colorings from affine planes
-proof techniques
-fine tuned results
-local colorings
-geometric versions
-hypergraph colorings
Étant donné un graphe G et des paires de sommets de G, le problème de déterminer s'il existe des chemins sommets-disjoints reliant ces paires est connu pour être NP-dur, même dans un graphe planaire. En revanche, il admet un algorithme linéaire si G est planaire et qu'il existe deux faces s et t telles que chaque paire de sommets contient un sommet incident à s et l'autre à t.
Nous nous plaçons dans ce cas, supposant en outre les arêtes de G munies d'une longueur positive. Nous montrons comment calculer des chemins sommets-disjoints reliant les paires de sommets requises, de sorte que la longueur totale des chemins soit minimale. L'algorithme a une complexité O(kn log n) où k est le nombre de paires de sommets et n est la complexité de G. La méthode repose sur des algorithmes de flot et de potentiel dans des graphes appropriés.
Travail en commun avec Alexander Schrijver, CWI, Amsterdam.
http://www.di.ens.fr/~colin/textes/04sdp.pdf
• 22/01/09 (salle 3.23) : Yann Vaxès : "Augmentation de graphe sous contrainte de diamètre"
Dans cet exposé, nous nous intéressons au problème de conception de réseau suivant : Etant donné un graphe G=(V,E), trouver un nombre minimum d'arêtes à ajouter à G pour obtenir un graphe G'=(V,E∪ E') dans lequel chaque paire de sommets est à distance au plus D. Nous présentons quelques résultats de complexité et d'approximation concernant ce problème et nous mettons en évidence la relation qui existe entre ce problème et le problème de R-domination. En particulier, dans le cas où le graphe de départ est un arbre, nous présentons des algorithmes polynomiaux qui permettent d'obtenir des solutions dont le coût est inférieur à 2 fois l'optimum dans le cas d'un diamètre pair et à 2+1/δ fois l'optimum dans le cas d'un diamètre impair. Nous présentons également quelques questions qui se posent lorsque l'on veut généraliser notre approche au cas des graphes planaires.
Travail en collaboration avec Victor Chepoi, Bertrand Estellon et Karim Nouioua.
Transparents de la présentation : ICI
• 05/02/09 (salle 3.23) : Vangelis Paschos : "Approximation by moderately exponential algorithms"
This talk presents a possible trade-off between polynomial approximation and exact computation. We show how using ideas from both fields one can design approximation algorithms for several combinatorial problems achieving ratios that cannot be achieved in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation. We study in particular maximum independent set and minimum vertex cover.
Transparents de la présentation : ICI
Le sujet de cet exposé est la résolution de problèmes de tournées de véhicules par des méthodes de génération de colonnes / Branch and Price. Dans une première partie, nous présenterons de manière didactique ces méthodes, leur fonctionnement, leurs atouts et leurs points faibles. Puis nous détaillerons quelques résultats de recherche concernant la résolution efficace du sous-problème.
Transparents de la présentation : ICI
The design of streaming (e.g. multimedia or network packet processing) applications must consider several optimizations such as the mimimization of the whole surface of the memory needed on a Chip. The minimum throughput of the output is usually fixed. In this talk, we present an original methodology to solve this problem.
The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and the places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput.
The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to the capacity. A first polynomial simple algorithm computing the minimum surface for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently. For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.
Transparents de la présentation : ICI
• 14/05/09 (salle 3.23) : Frédéric Havet : "Méthode probabiliste pour la coloration de graphes"
La méthode probabiliste est une des techniques les plus puisssantes en théorie des graphes. Depuis 40 ans, elle a permis de montrer de nombreux résultats importants. Dans cet exposé, nous montrerons différents outils probabilistes, des plus simples aux plus élaborés. Pour chacun d'entre eux, une application à la coloration de graphes sera donnée.
Transparents de la présentation : ICI
• 28/05/09 (salle 3.23) : Vincent T'Kindt : "L'Ordonnancement Multicritère : Théorie et Modèles"
Lors de ce séminaire je m'attacherai à donner une vision des problèmes que l'on peut rencontrer lorsqu'on aborde le domaine de l'ordonnancement multicritère : définition d'optimalité et implication pour les problèmes d'ordonnancement, comment résoudre en pratique un problème multicritère, ainsi que quelques considérations à propos de l'énumération des optima de Pareto. Dans une seconde partie, je présenterai quelques modèles émergents dans la littérature ainsi qu'un état de l'art. Pour ces modèles des algorithmes basiques seront présentés
Transparents de la présentation : ICI
Nous nous penchons sur le problème du calcul de la force d'un graphe. Nous décrivons la première formulation polyhédrale pour le calcul de la force pondérée d'un graphe de taille polynomiale en la taille du problème, à savoir O(mn), où n est le nombre de sommets et m le nombre d'arètes du graphe. Nous décrivons aussi un FPTAS surprenamment simple qui donne la force d'un graphe à un facteur 1+ε près en temps $O(m\log²(n)\log(\frac{m}{n})/ε²)$ et en espace O(m), dépassant d'un facteur d'environ min(n√m,n^{5/3}) le meilleur algortihme connu de Trubin associé à l'algorithme postérieur de Goldberg et Rao pour le flot maximum et d'environ σ(G) le FPTAS de Plotkin, Shmoys, et Tardos.
Transparents de la présentation : ICI
How big can the difference between the chromatic number and clique number be in a graph on at most n vertices? Can the extremal graphs be explored? While computational problems related to this chromatic gap are hopeless, an interplay between Ramsey theory and matching theory leads to a simple and (almost) exact formula for the maximum of this difference in terms of Ramsey numbers. As a consequence, the Ramsey graphs for R(3; :) have high matchability and connectivity properties.
Joint work with Nicolas Trotignon and Andras Gyarfas
Transparents de la présentation : ICI
• 18/06/10 (salle 3.23) : Hans Kellerer : "Symmetric quadratic knapsacks and scheduling problems"
We consider a special knapsack problem for minimizing a symmetric quadratic function. This knapsack problem is related to several single machine scheduling problems, e. g. the problem of minimizing the total weighted earliness and tardiness with respect to a common due date and minimizing the total weighted completion time for a non-availability period. It is shown how to construct a fully polynomial time approximation scheme (FPTAS) with strongly polynomial running time.