On a weighted linear matroid intersection algorithm by Deg-Det computation
- PDF / 4,336,093 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 175 Views
On a weighted linear matroid intersection algorithm by Deg‑Det computation Hiroki Furue1 · Hiroshi Hirai1 Received: 30 August 2019 / Revised: 13 February 2020 © The JJIAM Publishing Committee and Springer Japan KK, part of Springer Nature 2020
Abstract In this paper, we address the weighted linear matroid intersection problem from computation of the degree of the determinant of a symbolic matrix. We show that a generic algorithm computing the degree of noncommutative determinants, proposed by the second author, becomes an O(mn3 log n) time algorithm for the weighted lin‑ ear matroid intersection problem, where two matroids are given by column vectors of n × m matrices A, B. We reveal that our algorithm is viewed as a “nonstandard” implementation of Frank’s weight splitting algorithm for linear matroids. This gives a linear algebraic reasoning to Frank’s algorithm. Although our algorithm is slower than existing algorithms in the worst case estimate, it has a notable feature. Con‑ trary to existing algorithms, our algorithm works on different matroids represented by another “sparse” matrices A0 , B0 , which skips unnecessary Gaussian eliminations for constructing residual graphs. Keywords Combinatorial optimization · Polynomial time algorithm · Weighted matroid intersection · The degree of determinant · Weight splitting Mathematics Subject Classification 68W40
1 Introduction Several basic combinatorial optimization problems have linear algebraic formu‑ lations. It is classically known [2] that the maximum cardinality of a matching in a bipartite graph G = (U, V;E) with color classes U = [n], V = [n� ] is equal to the ∑ rank of the matrix A = e∈E Ae xe , where xe (e ∈ E) are variables and Ae is an n × n� * Hiroki Furue [email protected]‑tokyo.ac.jp Hiroshi Hirai [email protected]‑tokyo.ac.jp 1
Department of Mathematical Informatics, Graduate School of Information Science and Technology, The University of Tokyo, Tokyo 113‑8656, Japan
13
Vol.:(0123456789)
H. Furue, H. Hirai
matrix with (Ae )ij ∶= 1 if e = ij and zero otherwise. Such a rank interpretation is known for the linear matroid intersection, nonbipartite matching, and linear matroid matching problems; see [13]. The degree of the determinant of a polynomial (or rational) matrix is a weighted counter part of rank, and can formulate weighted versions of combinatorial opti‑ mization problems. The maximum weight perfect matching problem in a bipartite graph G = ([n], [n];E) with integer weights ce (e ∈ E) corresponds to computing the ∑ degree degt det A(t) of the determinant of the (rational) matrix A(t) ∶= e∈E Ae xe tce . Again, the weighted linear matroid intersection, nonbipartite matching, and linear matroid matching problems admit such formulations. Inspired by the recent advance [6, 10] of a noncommutative approach to sym‑ bolic rank computation, the second author [8] introduced the problem of com‑ puting the degree degt DetA(t) of the Dieudonné determinant DetA(t) of a matrix ∑ A(t) = i Ai (t)xi , where xi are pairwise noncommutative variables a
Data Loading...
