Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present a new algebraic algorithm for the classical problem of weighted matroid intersection. This problem generalizes numerous well-known problems, such as bipartite matching, network flow, etc. Our algorithm has running time Õ(nr^ω-1W1+ε) for linear matroids with n elements and rank r, where ω is the matrix multiplication exponent, and W denotes the maximum weight of any element. This algorithm is the fastest known when W is small. Our approach builds on the recent work of Sankowski (2006) for Weighted Bipartite Matching and Harvey (2006) for Unweighted Linear Matroid Intersection.

REFERENCES

• 1: M. Aigner and T. A. Dowling. Matching theory for combinatorial geometries. Transactions of the American Mathematical Society, 158(1):231--245, July 1971.
• 2: C Brezovec , Gerard Cornuéjols , Fred Glover, Two algorithms for weighted matroid intersection, Mathematical Programming: Series A and B, v.36 n.1, p.39-53, Oct. 1986 [doi>10.1007/BF02591988]
• 3: Prasad Chalasani , Rajeev Motwani, Approximating Capacitated Routing and Delivery Problems, SIAM Journal on Computing, v.28 n.6, p.2133-2149, Dec. 1999 [doi>10.1137/S0097539795295468]
• 4: William J. Cook , William H. Cunningham , William R. Pulleyblank , Alexander Schrijver, Combinatorial optimization, John Wiley & Sons, Inc., New York, NY, 1998
• 5: J. Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Schönheim, editors, Combinatorial Structures and Their Applications, pages 69--87. Gordon and Breach, 1970.
• 6: J. Edmonds. Matroids and the greedy algorithm. Mathematical Programming, 1:127--136, 1971.
• 7: J. Edmonds. Matroid intersection. In P. L. Hammer, E. L. Johnson, and B. H. Korte, editors, Discrete Optimization I, volume 4 of Annals of Discrete Mathematics, pages 39--49. North-Holland, 1979.
• 8: A. Frank. A weighted matroid intersection algorithm. Journal of Algorithms, 2(4):328--336, 1981.
• 9: S. Fujishige. A primal approach to the independent assignment problem. Journal of the Operations Research Society of Japan, (20):1--15, 1977.
• 10: S. Fujishige. Submodular Functions and Optimization, volume 58 of Annals of Discrete Mathematics. Elsevier, second edition, 2005.
• 11: H. N. Gabow , R. E. Tarjan, Faster scaling algorithms for network problems, SIAM Journal on Computing, v.18 n.5, p.1013-1036, Oct. 1989 [doi>10.1137/0218069]
• 12: Harold N. Gabow , Ying Xu, Efficient theoretic and practical algorithms for linear matroid intersection problems, Journal of Computer and System Sciences, v.53 n.1, p.129-147, Aug. 1996 [doi>10.1006/jcss.1996.0054]
• 13: Michel X. Goemans, Minimum Bounded Degree Spanning Trees, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.273-282, October 21-24, 2006 [doi>10.1109/FOCS.2006.48]
• 14: Nicholas J. A. Harvey, Algebraic Structures and Algorithms for Matching and Matroid Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.531-542, October 21-24, 2006 [doi>10.1109/FOCS.2006.8]
• 15: Nicholas J. A. Harvey , David R. Karger , Kazuo Murota, Deterministic network coding by matrix completion, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: Refael Hassin , Asaf Levin, An Efficient Polynomial Time Approximation Scheme for the Constrained Minimum Spanning Tree Problem Using Matroid Intersection, SIAM Journal on Computing, v.33 n.2, p.261-268, 2004 [doi>10.1137/S0097539703426775]
• 17: M. Iri. Applications of matroid theory. In A. Bachem, M. Grötschel, and B. Korte, editors, Mathematical Programming: The State of the Art, pages 158--201. 1983.
• 18: M. Iri and N. Tomizawa. An algorithm for finding an optimal "independent assignment". Journal of the Operations Research Society of Japan, 19:32--57, 1976.
• 19: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
• 20: S. Krogdahl. A combinatorial proof for a weighted matroid intersection algorithm. Technical Report Computer Science Report 17, Institute of Mathematical and Physical Sciences, University of Tromsø, 1976.
• 21: E. L. Lawler. Matroid intersection algorithms. Mathematical Programming, 9:31--56, 1975.
• 22: Marcin Mucha , Piotr Sankowski, Maximum Matchings via Gaussian Elimination, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.248-255, October 17-19, 2004 [doi>10.1109/FOCS.2004.40]
• 23: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 24: K. Murota. Matrices and Matroids for Systems Analysis. Springer-Verlag, 2000.
• 25: Kazuo Murota, Discrete convex analysis, Mathematical Programming: Series A and B, v.83 n.3, p.313-371, Nov. 1, 1998 [doi>10.1007/BF02680565]
• 26: Piotr Sankowski, Processor efficient parallel matching, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073994]
• 27: P. Sankowski. Weighted bipartite matching in matrix multiplication time. In Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006.
• 28: A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, 2003.
• 29: Arne Storjohann, High-order lifting and integrality certification, Journal of Symbolic Computation, v.36 n.3-4, p.613-648, September 2003 [doi>10.1016/S0747-7171(03)00097-X]