Premium
On the cycle polytope of a directed graph and its relaxations
Author(s) -
Balas Egon,
Stephan Rüdiger
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20304
Subject(s) - polytope , combinatorics , mathematics , birkhoff polytope , digraph , tournament , travelling salesman problem , polyhedral combinatorics , graph , complete graph , transitive relation , discrete mathematics , algorithm , geometry , convex set , convex optimization , regular polygon
We continue the investigation of the cycle polytope of a digraph begun by Balas and Oosten (Networks 36 (2000), 34–46) and derive a rich family of facets that cut off the origin and are not related to facets of the traveling salesman polytope. This disproves a claim in (Balas and Oosten 36 (2000), 34–46) that the only such facets are those defined by the linear ordering inequalities. After examining the relationship between the cycle polytope, its dominant, and the upper cycle polyhedron, we turn to the polar relationship between cycles and permutations or transitive tournaments. Our central result is a characterization of the relationship between facets of the dominant of the cycle polytope, facets of the cycle polytope that cut off the origin, and vertices of the linear relaxation of the transitive tournament polytope. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009