Abstract: | It is proved that, for any r ∈ { 2n, 2n + 1,…, 3n−2} and only for such r, the polytope of a three-index axial assignment problem
of order n, n ≥ 2, contains completely r-noninteger vertices (r-CNVs), i.e., vertices such that all their positive components
are fractional and their number equals r. For each r ∈ {2n, 2n + 1,…, 3n −2}, all the types of r-CNVs are characterized and
the combinatorial properties of completely r-noninteger vertices of the polytope are studied.
__________
Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 33–44, January–February 2007. |