Skip to main content
Article
Tropical Determinant on Transportation Polytopes
Linear Algebra and its Applications
  • Sailaja Gajula, Indiana University
  • Ivan Soprunov, Cleveland State University
  • Jenya Soprunova, Kent State University
Document Type
Article
Publication Date
2-20-2015
Disciplines
Abstract

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.

Comments

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

DOI
10.1016/j.laa.2015.01.036
Version
Postprint
Creative Commons License
Creative Commons Attribution-Noncommercial-No Derivative Works 4.0
Citation Information
Sailaja Gajula, Ivan Soprunov and Jenya Soprunova. "Tropical Determinant on Transportation Polytopes" Linear Algebra and its Applications Vol. 475 Iss. 15 (2015) p. 28 - 44 ISSN: 0024-3795
Available at: http://works.bepress.com/ivan-soprunov/11/