ISSN:
1436-4646
Keywords:
Facets of Polyhedra
;
Linear Ordering Problem
;
Triangulation Problem
;
Permutation Problem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract LetD n be the complete digraph onn nodes, and letP LO n denote the convex hull of all incidence vectors of arc sets of linear orderings of the nodes ofD n (i.e. these are exactly the acyclic tournaments ofD n ). We show that various classes of inequalities define facets ofP LO n , e.g. the 3-dicycle inequalities, the simplek-fence inequalities and various Möbius ladder inequalities, and we discuss the use of these inequalities in cutting plane approaches to the triangulation problem of input-output matrices, i.e. the solution of permutation resp. linear ordering problems.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582010
Permalink