Idioma:

0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets

Fiorini, Samuel

SIAM journal on discrete mathematics, 2006-10, Vol.20 (4), p.893-912 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
0, 1/2‐Cuts and the Linear Ordering Problem: Surfaces That Define Facets
Autor: Fiorini, Samuel
Assuntos: Inequality ; Integer programming ; Polytopes
É parte de: SIAM journal on discrete mathematics, 2006-10, Vol.20 (4), p.893-912
Descrição: We find new facet-defining inequalities for the linear ordering polytope generalizing the well-known Mobius ladder inequalities. Our starting point is to observe that the natural derivation of the Mobius ladder inequalities as $\{0,\frac{1}{2}\}$-cuts produces triangulations of the Mobius band and of the corresponding (closed) surface, the projective plane. In that sense, Mobius ladder inequalities have the same "shape" as the projective plane. Inspired by the classification of surfaces, a classic result in topology, we prove that a surface has facet-defining $\{0,\frac{1}{2}\}$-cuts of the same "shape" if and only if it is nonorientable.
Editor: Philadelphia: Society for Industrial and Applied Mathematics
Idioma: Inglês

Voltar para lista de resultados