More facets from fences for linear ordering and acyclic subgraph polytopes

Preprint
Publisher Website
Google Scholar
    • preprint
      • Published in RePEc
Abstract
We present new facets for the linear ordering polytope. These new facets generalize facets induced by sub graphs called fences, introduced by Grotschel, Junger and Reinelt (1985), and augmented fences, introduced by McLennan (1990). One novelty of the facets introduced here is that each sub graph induces not one but a family of facets, which are not generally rank inequalities. Indeed, we provide the smallest known example of a facet-representing inequality for the linear ordering polytope that is not a rank inequality. Gilboa (1990) introduced the diagonal inequalities for the linear ordering polytope, and Fishburn (1991) posed the question of identifying precisely which diagonal inequalities represent facets. We completely resolve Fishburn's question. Some of our results can be transported to the acyclic subgraph polytope. These new facets for the acyclic subgraph polytope are the first ones that are not represented by rank inequalities.
All Related Versions

This publication has 0 references indexed in Scilit: