Two algorithms for weighted matroid intersection.(English)Zbl 0632.90045
Given a set E with finite cardinality n, two matroids \(M_ 1\) and \(M_ 2\) and a weight function w defined on E, the authors develop a new algorithm to find a maximal weight intersection with cardinality k. If k is maximal the complexity of the algorithm is \(O(nr(r+c+\log n))\) where r is the maximum of the ranks of E in \(M_ 1\) and \(M_ 2\), respectively, and c is the complexity of an oracle which either establishes independence of \(I+e\) or finds the fundamental circuit for all intersections I and \(e\in E\setminus I\). This complexity bound improves the bounds of previous algorithms. The proofs which establish the validity of the algorithm are easier to understand than the proofs in most of the preceding publications on the subject.
Reviewer: H.Hamacher
MSC:
| 90C10 | Integer programming |
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 68Q25 | Analysis of algorithms and problem complexity |
Cite
Full Text:DOI
References:
| [1] | C. Brezovec, G. Cornuéjols and F. Glover, ”Generalized alternating cycles, shortest paths, and irreducible trees,” forthcoming paper. ·Zbl 0665.90076 |
| [2] | J. Edmonds, ”Submodular functions, matroids and certain polyhedra,” in: R. Guy, ed.,Combinatorial Structures and their Applications, Proceedings of the Calgary International Conference (Gordon and Breach, New York, 1970) pp. 69–87. ·Zbl 0268.05019 |
| [3] | J. Edmonds, ”Matroid intersection”,Annals of Discrete Mathematics 4 (1979) 39–49. ·Zbl 0416.05025 ·doi:10.1016/S0167-5060(08)70817-3 |
| [4] | A. Frank, ”A weighted matroid intersection algorithm”,Journal of Algorithms 2 (1981) 328–336. ·Zbl 0484.05025 ·doi:10.1016/0196-6774(81)90032-8 |
| [5] | M.L. Fredman and R.E. Tarjan, ”Fibronacci heaps and their uses in improved network optimization algorithms”,Proceedings of the 25th Annual IEEE Symposium on the Foundations of Computer Science (1984) 338–346. |
| [6] | S. Fujishige, ”A primal approach to the independent assignment problem”,Journal of the Operations Research Society of Japan 20 (1977) 1–15. ·Zbl 0364.90102 |
| [7] | F. Glover, ”The generalized quasi-greedy algorithm for constrained minimum weight matroid bases”, MSIS Series, Report No. 85-1, Graduate School of Business University of Colorado (Boulder, 1985). |
| [8] | M. Iri and N. Tomizawa, ”An algorithm for finding an optimal independent assignment”,Journal of the Operations Research Society of Japan 19 (1976) 32–57. ·Zbl 0346.90062 |
| [9] | E.L. Lawler,Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976). ·Zbl 0413.90040 |
| [10] | J.B. Orlin and J. Vande Vate, ”On a ’primal’ matroid intersection algorithm”, Sloan School Technical Report, MIT (Cambridge, 1984). ·Zbl 0813.90097 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
