Tropical determinant of integer doubly-stochastic matrices

被引：1

作者：

Dinitz, Thomas ^{[2
]}

Hartman, Matthew ^{[3
]}

Soprunova, Jenya ^{[1
]}

机构：

[1] Kent State Univ, Dept Math Sci, Kent, OH 44242 USA

[2] Colgate Univ, Hamilton, NY 13346 USA

[3] Xavier Univ, Cincinnati, OH 45207 USA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2012年 / 436卷 / 05期

基金：

美国国家科学基金会;

关键词：

Tropical determinant; Birkhoff polytope; Integer linear programming;

D O I：

10.1016/j.laa.2011.07.033

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

Let D(m, n) be the set of all the integer points in the m-dilate of the Birkhoff polytope of doubly-stochastic n x n matrices. In this paper we find the sharp upper bound on the tropical determinant over the set D(m, n). We define a version of the tropical determinant where the maximum over all the transversals in a matrix is replaced with the minimum and then find the sharp lower bound on thus defined tropical determinant over D(m, n). (C) 2011 Elsevier Inc. All rights reserved.

引用

页码：1212 / 1227

页数：16

共 8 条

[1]

Birkhoff Garrett, 1946, U NAC TUCUMN REV, V5

[2]

Burkard R., 2009, ASSIGNMENT PROBLEMS

[3] Max algebra and the linear assignment problem [J].

Burkard, RE ;

Butkovic, P .

MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) :415-429

[4]

EGORYCHEV GP, 1981, ADV MATH, V42, P299, DOI 10.1016/0001-8708(81)90044-X

[5]

Falikman D.I., 1981, MAT ZAMETKI, V29, p[931, 957]

[6]

Falikman D. I., 1981, MAT ZAMETKI, V29, P957

[7]

Hall Philip, 1935, J LOND MATH SOC, V10, P10

[8]

Kuhn H.W., 1955, NAV RES LOG, V2, P8397

← 1 →