Fast greedy for linear matroids
Fast greedy for linear matroids
复制标题
快速贪婪线性拟阵
DOI：
10.1137/1.9781611975482.32
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Nguyen, H.
中科院分区：
文献类型：
--
作者：
Nguyen, H.
拟阵的一个基本的算法结果是，最大的重量基地可以使用贪婪算法计算。对于显式表示的拟阵，一个重要的问题是计算这样一个基的时间复杂度。已知可以在线性表示的非零元素的数目plusrω中几乎线性地在时间上计算它，其中是拟阵的秩，ω是矩阵乘法指数。在这项工作中，我们给出了一个替代算法相同的任务。
A fundamental algorithmic result for matroids is that the maximum weight base can be computed using the greedy algorithm. For explicitly represented matroids an important question is the time complexity of computing such a base. It is known that one can compute it in time almost linear in the number of non-zero entries of the linear representation plusrω, whereris the rank of the matroid and ω is the matrix multiplication exponent. In this work, we give an alternative algorithm for the same task.