Document Type

Article

Publication Date

2-20-2015

Publication Title

Linear Algebra and its Applications

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 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Volume

475

Issue

15

Included in

Mathematics Commons

Share

COinS