Intersection of Two Matroids: (Condensed) Border Graphs and Ranking
Paolo M. Camerini, Horst W. Hamacher · SIAM Journal on Discrete Mathematics · 1989
Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.
SIAM Journal on Discrete Mathematics · Society for Industrial and Applied Mathematics · article · 1989
Abstract
Given two matroids $M_1 = (E,\mathcal{J}_1 )$ and, $M_2 = (E,\mathcal{J}_2 )$, three algorithms for finding K best intersections $I_1 ,I_2 , \cdots ,I_K $ are presented. The first version is a straightforward application of a general procedure due to Murty and Lawler. The complexity for finding $I_2 , \cdots ,I_k $ is $O(Km^2 R(R + c(m) + \log m))$ where m is the number of elements in $E, R = \min \{ r_1 (E),r_2 (E)\} $, and $c(m)$ is the complexity of an independence oracle. By using maximum weighted border paths to compute second best intersections of modified matroids, this bound is reduced to $O(K(m^3 + mRc(m))$.
Finally, a condensed version of the border graph is proposed to further improve the bound to $O(KmRc(m))$. The latter idea can also be used to find the optimal intersection $I_1 $ in $O(mR^2 c(m))$ time, which is competitive with recent matroid intersection algorithms by Frank [J. Algorithms, 2 (1981), pp. 328–336] and Brezovec, Cornuejols, and Glover [Math. Programming, 36 (1986), pp. 39–53].
Open the resolved locator · 10.1137/0402002
Metadata licence: OpenAlex metadata (CC0)