论文标题
通过非交通等级的分数线性矩阵均衡的代数算法
Algebraic Algorithms for Fractional Linear Matroid Parity via Non-commutative Rank
论文作者
论文摘要
矩阵表示是设计有效算法的强大工具，用于组合优化问题，例如匹配，线性矩阵相交和奇偶校验。在本文中，我们使用非交通级别（NC级）的概念启动矩阵表示的研究，该概念最近引起了埃德蒙兹问题研究的关注。我们揭示了线性矩阵平等的矩阵表示的NC级别对应于分数线性矩阵奇偶校验的最佳值：线性矩阵奇偶校验的半融合松弛。根据我们的表示，我们通过构建一种新技术来将搜索性降低降低纳入通过NC级别表示的半集成问题，来提出一种用于分数线性矩阵奇偶校验问题的代数算法。我们进一步提出了一种更快的划分和争议算法，用于查找最大的分数矩阵匹配和用于查找双重最佳解决方案的代数算法。它们共同导致了加权分数线性矩阵奇偶校验问题的代数算法。与现有算法相比，我们的算法明显简单，更快。
Matrix representations are a powerful tool for designing efficient algorithms for combinatorial optimization problems such as matching, and linear matroid intersection and parity. In this paper, we initiate the study of matrix representations using the concept of non-commutative rank (nc-rank), which has recently attracted attention in the research of Edmonds' problem. We reveal that the nc-rank of the matrix representation of linear matroid parity corresponds to the optimal value of fractional linear matroid parity: a half-integral relaxation of linear matroid parity. Based on our representation, we present an algebraic algorithm for the fractional linear matroid parity problem by building a new technique to incorporate the search-to-decision reduction into the half-integral problem represented via the nc-rank. We further present a faster divide-and-conquer algorithm for finding a maximum fractional matroid matching and an algebraic algorithm for finding a dual optimal solution. They together lead to an algebraic algorithm for the weighted fractional linear matroid parity problem. Our algorithms are significantly simpler and faster than the existing algorithms.
