论文标题
用于计算决定因素程度的成本规模算法
A cost-scaling algorithm for computing the degree of determinants
论文作者
论文摘要
在本文中，我们解决了$ \ mathop {\ rm d det} a $dieudonné级别的$ \ mathop {\ rm det} a $ of \ [a = \ sum_ { $ \ mathbb {k} $，$ x_k $是非交换变量，$ t $是一个变量通勤，$ x_k $，$ c_k $是整数，并且该学位用于$ t $。这个问题概括了非交互性Edmonds的问题和基本组合优化问题，包括加权线性矩阵相交问题。结果表明，$ \ mathop {\ rm d det} a $是通过在欧几里得建筑物上的离散凸优化获得的。我们通过合并成本缩放技术来扩展此框架，并证明可以在$ n，m，m，log_2 c $的时间内计算$ \ mathop {\ rm d det} a $，其中$ c：= \ max_k | c_k | c_k | $。我们给出了$ \ mathop {\ rm deg det} $的多面解释，该解释说$ \ mathop {\ rm deg det} a $是通过对目标矢量$ c =（c_k）$的积分polytope的线性优化给出的。基于它，我们表明我们的算法成为一种强烈的多项式。我们将此结果应用于代数组合优化问题，该问题是由具有$ 2 \ times 2 $ -submatrix结构的符号矩阵引起的。
In this paper, we address computation of the degree $\mathop{\rm deg Det} A$ of Dieudonné determinant $\mathop{\rm Det} A$ of \[ A = \sum_{k=1}^m A_k x_k t^{c_k}, \] where $A_k$ are $n \times n$ matrices over a field $\mathbb{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 $\mathop{\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 $\mathop{\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 $\mathop{\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.
