Abstract
In this paper we discuss the polyhedral structure of polytopes associated with the linear-ordering problem. We give explicit lists of facets of small linear-ordering polytopes for complete digraphs on up to seven nodes. For the latter we give a description that we believe to be complete.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. J. Bowman (1972), Permutation polyhedra,SIAM J. Appl. Math 22, 580–589.
J. S. de Cani (1969), Maximum likelihood paired comparison ranking by linear programming,Biometrika 56, 537–545.
T. Christof (1991), Ein Verfahren zur Transformation zwischen Polyederdarstellungen, Diplomarbeit, Universität Augsburg.
T. Christof, M. Jünger, and G. Reinelt (1991), A Complete Description of the Traveling Salesman Polytope on 8 Nodes,Oper. Res. Lett. 10, 497–500.
T. Dridi (1980), Sur les distribution binaires associees a des distributions ordinales,Math. Sci. Humaines 69, 15–31.
P. C. Fishburn (1990), Binary probabilities induced by rankings,SIAM J. Discrete Math. 3, 478–488.
P. C. Fishburn (1991), Induced Binary Probabilities and the Linear Ordering Polytope: A Status Report, AT & T Bell Laboratories.
M. Grötschel, M. Jünger, and G. Reinelt (1984), A cutting plane algorithm for the linear ordering problem,Oper. Res. 32, 1195–1220.
M. Grötschel, M. Jünger, and G. Reinelt (1985), Facets of the linear ordering polytope,Math. Programming 33, 43–60.
D. Hausmann (1980),Adjacency on Polytopes in Combinatorial Optimization, Hain, Meisenheim.
J. Leung and J. Lee (1990), Reinforcing Old Fences Gives New Facets, Report Yale University.
G. Reinelt (1985),The Linear Ordering Problem: Algorithms and Applications, Research and Exposition in Mathematics, Vol. 8, Heldermann-Verlag, Berlin.
R. Suck (1991), Geometric and Combinatorial Properties of the Polytope of Binary Choice Probabilities, Report, Universität Osnabrück.
S. N. Tschernikov (1971),Lineare Ungleichungen, Deutscher Verlag der Wissenschaften, Berlin.
H. P. Young (1978), On permutations and permutation polytopes,Math. Programming Stud. 8, 128–140.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Reinelt, G. A note on small linear-ordering polytopes. Discrete Comput Geom 10, 67–78 (1993). https://doi.org/10.1007/BF02573963
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02573963