Résumé de rapport du LIF

Téléchargement / Download : pdf 260k , ps.gz 244k , bibtex

Abstract

The integer programming models known as set packing and set covering have a wide range of applications, many of which arise in the context of graph theory. Sometimes, because of the special structure of the constraint matrix, the natural linear programming relaxation yields an optimal solution that is integral, thus solving the problem. Sometimes, both the linear programming relaxation and its dual have integer optimal solutions. Under which conditions do such integrality properties hold? This question is of both theoretical and practical interest. Min-max theorems, polyhedral combinatorics and graph theory all come together in this rich area of discrete mathematics. In addition to min-max and polyhedral results, some of the deepest results in this area come in two flavors: "excluded structure" characterizations and "decomposition" results. These notes provide an introduction to this area. In particular, they survey the celebrated Strong Perfect Graph Conjecture and its recent solution by Chudnovsky, Robertson, Seymour and Thomas, and Lehman's characterization of ideal clutters. The monograph "Combinatorial Optimization: Packing and Covering" by Cornuéjols, CBMS 74, SIAM (2001) provides background material.

Keywords

Combinatorial optimization, packing, covering, ideal clutter, perfect graph.

Résumé

Les problèmes de recouvrement et d'empaquetage ont de nombreuses applications, en particulier en théorie des graphes. Parfois, en raison de la structure particulière de la matrice des contraintes, la relaxation naturelle de ces problèmes sous forme d'un programme linéaire produit une solution optimale entière, ce qui résoud donc le problème initial. Sous quelle conditions a-t-on cette propriété d'intégralité ? Cette question a un intérêt à la fois théorique et pratique. Les théorèmes Min-Max, la combinatoire polyèdrale et la théorie des graphes se retrouvent dans ce domaine riche des mathématiques discrètes. A côté des théorèmes polyèdraux et Min-Max qui sont souvent très élégants, les résultats les plus profonds dans ce domaine ont tendance à se présenter sous deux formes: caractérisation par "structures exclues" et théorèmes de "décomposition". Ces notes présentent une introduction à ce domaine. En particulier elles survolent la célèbre conjecture des graphes parfaits et sa solution récente par Chudnovsky, Robertson, Seymour and Thomas, et la caractérisation de Lehman des hypergraphes idéaux.

Mots clés

Optimisation combinatoire, empaquetage, recouvrement, hypergraphe, idéal, graphe parfait.

Bibtex

@TECHREPORT{15-2003,
    AUTHOR	= {Gérard Cornuéjols},
    TITLE	= {{Graphs and Combinatorial Optimization}},
    INSTITUTION	= {{LIF}},
    ADDRESS	= {Marseille, France},
    TYPE	= {Research report},
    NUMBER	= {15-2003},
    MONTH	= {11},
    YEAR	= {2003},
    NOTE	= {http://pageperso.lif.univ-mrs.fr/~edouard.thiel/RESP/Rapports/15-2003.html},
}