Tropical Determinant on Transportation Polytopes

Authors

Sailaja Gajula, Indiana University
Ivan Soprunov, Cleveland State UniversityFollow
Jenya Soprunova, Kent State UniversityFollow

Document Type

Article

Publication Date

2-20-2015

Publication Title

Linear Algebra and its Applications

Abstract

Let D^k,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 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.

Comments

Ivan Soprunov is partially supported by NSA Grant H98230-13-1-0279.

Repository Citation

Gajula, Sailaja; Soprunov, Ivan; and Soprunova, Jenya, "Tropical Determinant on Transportation Polytopes" (2015). Mathematics and Statistics Faculty Publications. 276.
https://engagedscholarship.csuohio.edu/scimath_facpub/276

DOI

10.1016/j.laa.2015.01.036

Version

Postprint

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.

Volume

475

Issue

15