Tropical determinant on transportation polytope

Abstract

Let ${\mathcal{D}}^{k,l}(m,n)$ be the set of all the integer points in the transportation polytope of $kn\times ln$ matrices with row sums $lm$ and column sums $km$. In this paper we find the sharp lower bound on the tropical determinant over the set ${\mathcal{D}}^{k,l}(m,n)$. This integer piecewise-linear programming problem in arbitrary dimension turns out to be equivalent to an integer non-linear (in fact, quadratic) optimization problem in dimension two. We also compute the sharp upper bound on a modification of the tropical determinant, where the maximum over all the transversals in a matrix is replaced with the minimum.

16 pages, 2 figures

References in corpus (1)

• Tropical Determinant of Integer Doubly-Stochastic Matrices