In this paper, we address computation of the degree \rm deg Det A of Dieudonn\'e determinant \rm Det A of \[ A = k=1^m A_k x_k t^{c_k}, \] where A_k are n \times n matrices over a field K, x_k are noncommutative variables, t is a variable commuting  x_k, c_k are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that \rm deg Det A is obtained by a discrete convex optimization on a Euclidean building. We extend this framework by incorporating a cost scaling technique, and show that \rm deg Det A can be computed in time polynomial of n,m,\log_2 C, where C:= \max_k |c_k| , which says that \rm deg Det A is given by linear optimization over an integral polytope with respect to objective vector c = (c_k). Based on it, we show that our algorithm becomes a strongly polynomial one} . We apply this result to an algebraic combinatorial optimization problem arising from a symbolic matrix having 2 \times 2-submatrix structure.
In this paper, we address computation of the degree \rm deg Det A of Dieudonn\'e determinant \rm Det A of \[ A = k=1^m A_k x_k t^{c_k}, \] where A_k are n \times n matrices over a field K, x_k are noncommutative variables, t is a variable commuting with x_k, c_k are integers, and the degree is considered for t. This problem generalizes noncommutative Edmonds' problem and fundamental combinatorial optimization problems including the weighted linear matroid intersection problem. It was shown that \rm deg Det A is obtained by a discrete convex optimization on a Euclidean building. We extend this framework by incorporating a cost scaling technique, and show that \rm deg Det A can be computed in time polynomial of n,m,\log_2 C, where C:= \max_k |c_k| . We give a polyhedral interpretation of \mathop{\rm deg Det, which says that \rm deg Det A is given by linear optimization over an integral polytope with respect to objective vector c = (c_k). Based on it, we show that our algorithm becomes a strongly polynomial one} . We apply this result to an algebraic combinatorial optimization problem arising from a symbolic matrix having 2 \times 2-submatrix structure.
A
with
A
. We give a polyhedral interpretation of \mathop{\rm deg Det