David Avis
RetourPublications
Cahiers du GERAD
An LP-digraph is a directed graph which consists of the vertices and edges of a polytope <i>P</i> directed by a linear function in general position. It is ...
référence BibTeX
Most examples of cycling in the simplex method are given without explanation of how they were constructed. An exception is Beale’s 1955 example built around...
référence BibTeXComputing Disjoint Paths on Polytopes
The Holt-Klee Condition states that there exist at least <i>d</i> vertex-disjoint strictly monotone paths from the source to the sink of a polytopal digraph ...
référence BibTeX
Hypermetric inequalities have many applications, most recently in the approximate solution of max-cut problems by linear and semidefinite programming. Howeve...
référence BibTeX
Dans une rubrique de la Revue Française de Recherche Opérationnelle intitulée <i>Problèmes plaisans et délectables</i> en hommage à l'oeuvre du 17ème siècle ...
référence BibTeX
We present a simple algorithm that finds a nonnegative solution to a system of linear inequalities. This algorithm can be taught to secondary or college leve...
référence BibTeX
We consider linear programming relaxations for the max cut problem in graphs, based on <i>k</i>-gonal inequalities. We show that the integrality ratio for ra...
référence BibTeX