research-article

Fast greedy for linear matroids

Author:

Huy L. NguyễnAuthors Info & Claims

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

Pages 516 - 524

Published: 06 January 2019 Publication History

Get Access

Abstract

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 plus r^ω, where r is the rank of the matroid and ω is the matrix multiplication exponent. In this work, we give an alternative algorithm for the same task.

References

[1]

H. Y. Cheung, T. C. Kwok, and L. C. Lau. Fast matrix rank algorithms and applications. Journal of the ACM (JACM), 60(5):31, 2013.

Digital Library

Google Scholar

[2]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251--280, 1990.

Digital Library

Google Scholar

[3]

J.-G. Dumas, C. Pernet, and Z. Sultan. Fast computation of the rank profile matrix and the generalized bruhat decomposition. Journal of Symbolic Computation, 83:187--210, 2017.

Google Scholar

[4]

H. N. Gabow and Y. Xu. Efficient theoretic and practical algorithms for linear matroid intersection problems. Journal of Computer and System Sciences, 53(1):129--147, 1996.

Digital Library

Google Scholar

[5]

N. J. Harvey. Algebraic algorithms for matching and matroid problems. SIAM Journal on Computing, 39(2):679--702, 2009.

Digital Library

Google Scholar

[6]

N. J. A. Harvey. Matchings, matroids and submodular functions. PhD thesis, Massachusetts Institute of Technology, 2008.

Digital Library

Google Scholar

[7]

C.-C. Huang, N. Kakimura, and N. Kamiyama. Exact and approximation algorithms for weighted matroid intersection. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 430--444. Society for Industrial and Applied Mathematics, 2016.

Digital Library

Google Scholar

[8]

F. Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296--303. ACM, 2014.

Digital Library

Google Scholar

[9]

A. Storjohann and S. Yang. Linear independence oracles and applications to rectangular and low rank linear systems. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 381--388, New York, NY, USA, 2014. ACM.

Digital Library

Google Scholar

Fast greedy for linear matroids
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Theory of computation

Recommendations

Stabilizers of Classes of Representable Matroids

Let M be a class of matroids representable over a field F. A matroid N M stabilizes M if, for any 3-connected matroid M M, an F-representation of M is uniquely determined by a representation of any one of its N-minors. One of the main theorems of this ...
Fork-decompositions of matroids

One of the central problems in matroid theory is Rota's conjecture that, for all prime powers q, the class of GF(q)-representable matroids has a finite set of excluded minors. This conjecture has been settled for q=<4 but remains open otherwise. Further ...
Lattice Path Bicircular Matroids
Abstract
Lattice path matroids and bicircular matroids are two well-known classes of transversal matroids. In the seminal work of Bonin and de Mier about structural properties of lattice path matroids, the authors claimed that lattice path matroids ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SODA '19: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms

January 2019

2993 pages

Program Chair:
Timothy M. Chan
University of Illinois at Urbana-Champaign

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2019

Check for updates

Qualifiers

Research-article

Conference

SODA '19

Sponsor:

SODA '19: Symposium on Discrete Algorithms

January 6 - 9, 2019

California, San Diego

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
52
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Recommendations

Stabilizers of Classes of Representable Matroids

Fork-decompositions of matroids

Lattice Path Bicircular Matroids