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ᵢ) denotes the number of nonzero entries in Mᵢ 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.
Tatsuya Terao (Thu,) studied this question.