Linear Algebra and its Applications
Let Dk,l(m, n)be the set of all the integer points in the transportation polytope of kn × 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 Dk,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.
Gajula, Sailaja; Soprunov, Ivan; and Soprunova, Jenya, "Tropical Determinant on Transportation Polytopes" (2015). Mathematics Faculty Publications. 276.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Ivan Soprunov is partially supported by NSA Grant H98230-13-1-0279.