# Faster Approximate Linear Matroid Intersection

Preprint · Tatsuya Terao

- Archive id: arxiv:2604.11725
- Published: 2026-04-13
- arXiv: https://arxiv.org/abs/2604.11725
- Source URL: https://arxiv.org/abs/2604.11725
- PDF: https://arxiv.org/pdf/2604.11725
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.