{"id":"arxiv:2604.11725","kind":"preprint","title":"Faster Approximate Linear Matroid Intersection","authors":["Tatsuya Terao"],"author_count":1,"year":2026,"published":"2026-04-13","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2604.11725","nct_id":null,"source_url":"https://arxiv.org/abs/2604.11725","archive_url":"https://space-kitty.com/papers/arxiv:2604.11725","updated":"2026-04-13","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2604.11725","abstract":"We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two $r \\times n$ matrices $M_1$ and $M_2$, and the objective is to find a largest set of columns that are linearly independent in both $M_1$ and $M_2$. We design a $(1 - \\varepsilon)$-approximation algorithm with time complexity $\\tilde{O}_{\\varepsilon}(\\mathrm{nnz}(M_1) + \\mathrm{nnz}(M_2) + r_{*}^ω)$, where $\\mathrm{nnz}(M_i)$ denotes the number of nonzero entries in $M_i$ for $i = 1, 2$, $r_{*}$ denotes the maximum size of a common independent set, and $ω< 2.372$ denotes the matrix multiplication exponent. Our approximation algorithm is faster than the exact algorithm by Harvey [FOCS'06 & SICOMP'09] and Cheung--Kwok--Lau [STOC'12 & JACM'13], which runs in $\\tilde{O}(\\mathrm{nnz}(M_1) + \\mathrm{nnz}(M_2) + n r_{*}^{ω- 1})$ time. We also develop a fast $(1 - \\varepsilon)$-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a $(1 - \\varepsilon)$-approximation algorithm for weighted linear matroid intersection with time complexity $\\tilde{O}_{\\varepsilon}(\\mathrm{nnz}(M_1) + \\mathrm{nnz}(M_2) + r_{*}^ω)$. Our algorithm improves upon the $(1 - \\varepsilon)$-approximation algorithm by Huang--Kakimura--Kamiyama [SODA'16 & Math. Program.'19], which runs in $\\tilde{O}_{\\varepsilon}(\\mathrm{nnz}(M_1) + \\mathrm{nnz}(M_2) + nr_{*}^{ω- 1})$ time. To obtain these results, we combine Quanrud's adaptive sparsification framework [ICALP'24] with a simple yet effective method for efficiently checking whether a given vector lies in the linear span of a subset of vectors, which is of independent interest.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}