Vertex structure of master corner polyhedra

zbMATH Open1274.52016arXiv1104.4569MaRDI QIDQ2857445FDOQ2857445

Publication date: 1 November 2013

Abstract: This paper focuses on vertices of the master corner polyhedra

P (G, g_{0}),

the core of the group-theoretical approach to integer linear programming. We introduce two combinatorial operations that transform each vertex of

P (G, g_{0})

to adjacent ones. This implies that for any

P (G, g_{0}),

there exists a subset of basic vertices, we call them support vertices, from which all others can be built. The class of support vertices is proved to be invariant under the automorphism group of

G,

so this basis can be further reduced to a subset of pairwise non-equivalent support vertices. Among other results, we characterize irreducible points of the master corner polyhedra, establish relations between an integer point and the nontrivial facets that pass through it, construct complete subgraphs of the graph of

P (G, g_{0}),

and show that these polyhedra are of diameter 2.

Full work available at URL: https://arxiv.org/abs/1104.4569

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

Cites Work

This page was built for publication: Vertex structure of master corner polyhedra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2857445)