Data: |
1997 |
Resum: |
In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytope P through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant of P. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedron P, g-mon (P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet of P. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. . |
Drets: |
Aquest material està protegit per drets d'autor i/o drets afins. Podeu utilitzar aquest material en funció del que permet la legislació de drets d'autor i drets afins d'aplicació al vostre cas. Per a d'altres usos heu d'obtenir permís del(s) titular(s) de drets. |
Llengua: |
Anglès |
Document: |
Article ; recerca ; Versió publicada |
Matèria: |
Polyhedral combinatorics ;
Monotone polyhedra ;
Submissive ;
Dominant |
Publicat a: |
Mathematical Programming, vol. 78 n. 1 (1997) p. 59-84, ISSN 0025-5610 |