Algebraic algorithms for fractional linear matroid parity via non-commutative rank
Algebraic algorithms for fractional linear matroid parity via non-commutative rank
复制标题
通过非交换秩实现分数线性拟阵奇偶校验的代数算法
DOI：
10.1137/1.9781611977554.ch161
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Soma Tasuku
中科院分区：
文献类型：
--
作者：
Oki Taihei;Soma Tasuku
矩阵表示是设计组合优化问题（例如匹配、线性拟阵交集和奇偶校验）的有效算法的强大工具。在本文中，我们利用非交换秩（nc-rank）的概念发起了矩阵表示的研究，该概念最近在埃德蒙兹问题的研究中引起了人们的关注。我们揭示了线性拟阵奇偶校验的矩阵表示的 nc-rank 对应于分数线性拟阵奇偶校验的最优值：线性拟阵奇偶校验的半积分松弛。基于我们的表示，我们通过构建一种新技术将搜索到决策简化合并到通过 nc-rank 表示的半积分问题中，提出了分数线性拟阵奇偶校验问题的代数算法。我们进一步提出了一种用于寻找最大分数拟阵匹配的更快的分而治之算法和一种用于寻找对偶最优解的代数算法。它们共同产生了用于加权分数线性拟阵奇偶校验问题的代数算法。我们的算法比现有算法明显更简单、更快。
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 noncommutative 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.