2026-10-01T07:51:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26075 2026-09-23T23:59:41Z ddc:004 open_access

Faster Approximate Linear Matroid Intersection Terao, Tatsuya Linear matroid intersection fast approximation algorithm We consider a fast approximation algorithm for the linear matroid intersection problem. In this problem, we are given two r × n matrices M₁ and M₂, and the objective is to find a largest set of columns that are linearly independent in both M₁ and M₂. We design a (1 - ε)-approximation algorithm with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}), where 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 Õ(nnz(M₁) + nnz(M₂) + n r_{*}^{ω - 1}) time. We also develop a fast (1 - ε)-approximation algorithm for the weighted version of the linear matroid intersection problem. In fact, we design a (1 - ε)-approximation algorithm for weighted linear matroid intersection with time complexity Õ_{ε}(nnz(M₁) + nnz(M₂) + r_{*}^{ω}). Our algorithm improves upon the (1 - ε)-approximation algorithm by Huang-Kakimura-Kamiyama [SODA'16 & Math. Program.'19], which runs in Õ_{ε}(nnz(M₁) + nnz(M₂) + 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Terao 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.39 urn:nbn:de:0030-drops-260756 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.39 eng https://creativecommons.org/licenses/by/4.0/legalcode