David Avis
BackPublications
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 ...
BibTeX reference
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...
BibTeX referenceComputing 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 ...
BibTeX reference
Hypermetric inequalities have many applications, most recently in the approximate solution of max-cut problems by linear and semidefinite programming. Howeve...
BibTeX reference
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 ...
BibTeX reference
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...
BibTeX reference
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...
BibTeX reference