论文标题
等级的次级加权矩阵相交
Subquadratic Weighted Matroid Intersection Under Rank Oracles
论文作者
论文摘要
Given two matroids $\mathcal{M}_1 = (V, \mathcal{I}_1)$ and $\mathcal{M}_2 = (V, \mathcal{I}_2)$ over an $n$-element integer-weighted ground set $V$, the weighted matroid intersection problem aims to find a common independent set $ s^{*} \ in \ mathcal {i} _1 \ cap \ mathcal {i} _2 $最大化$ s^{*} $的权重。在本文中，我们提出了一种简单的确定性算法，用于使用$ \ tilde {o}（nr^{3/4} \ log {w}）$等级查询，其中$ r $是$ r $的大小，是$ \ mathcal {m} $ _1 $ _ $ _ $和$ \ $ \ $ _的最大值。这改善了以前最著名的$ \ tilde {o}（nr \ log {w}）$算法由Lee，Sidford和Wong [focs'15]提供的，并且是第一个在标准独立性或等级独立性或等级独立性模型下多项式遇到的算法。本文的主要贡献是一种有效的算法，该算法在加权交换图中计算最短的路径树。
Given two matroids $\mathcal{M}_1 = (V, \mathcal{I}_1)$ and $\mathcal{M}_2 = (V, \mathcal{I}_2)$ over an $n$-element integer-weighted ground set $V$, the weighted matroid intersection problem aims to find a common independent set $S^{*} \in \mathcal{I}_1 \cap \mathcal{I}_2$ maximizing the weight of $S^{*}$. In this paper, we present a simple deterministic algorithm for weighted matroid intersection using $\tilde{O}(nr^{3/4}\log{W})$ rank queries, where $r$ is the size of the largest intersection of $\mathcal{M}_1$ and $\mathcal{M}_2$ and $W$ is the maximum weight. This improves upon the best previously known $\tilde{O}(nr\log{W})$ algorithm given by Lee, Sidford, and Wong [FOCS'15], and is the first subquadratic algorithm for polynomially-bounded weights under the standard independence or rank oracle models. The main contribution of this paper is an efficient algorithm that computes shortest-path trees in weighted exchange graphs.
