Abstract
An algorithmic characterization of a particular combinatorial optimization problem means that there is an algorithm that works exact if and only if applied to the combinatorial optimization problem under investigation. According to Jack Edmonds, the Greedy algorithm leads to an algorithmic characterization of matroids. We deal here with the algorithmic characterization of the intersection of two matroids. To this end we introduce two different augmentation digraphs for the intersection of any two independence systems. Paths and cycles in these digraphs correspond to candidates for improving feasible solutions. The first digraph gives rise to an algorithmic characterization of bipartite b-matching. The second digraph leads to a polynomial-time augmentation algorithm for the (weighted) matroid intersection problem and to a conjecture about an algorithmic characterization of matroid intersection.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Brezovec, G. Cornuejols, and F. Glover, Two algorithms for weighted matroid intersection, Mathematical Programming 36 (1986), 39–53.
C. Berge, Two theorems in graph theory, Proc. of the National Academy of Sciences (U.S.A.) 43 (1957), 842–844.
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, and A. Schrijver, Combinatorial optimization, Wiley-Interscience, New York, 1998.
P.M. Camerini and H.W. Hamacher, Intersection of two matroids: (condensed) border graphs and ranking, SIAM Journal on Discrete Mathematics 2 (1989), no. 1, 16–27.
J. Edmonds, Matroid partition, Math. Decision Sciences, Proceedings 5th Summer Seminary Stanford 1967, Part 1 (Lectures of Applied Mathematics 11) (1968), 335–345.
J. Edmonds, Submodular functions, matroids, and certain polyhedra, Combinatorial Structures and their Applications (R. K. Guy, H. Hanai, N. Sauer and J. Schönheim, eds.), Gordon and Brach, New York (1970), 69–87.
J. Edmonds, Matroids and the greedy algorithm, Mathematical Programming 1 (1971), 127–136.
J. Edmonds, Matroid intersection, Annals of Discrete Mathematics 4 (1979), 39–49.
S. Fujishige, A primal approach to the independent assignment problem, Journal of the Operations Research Society of Japan 20 (1977), 1–15.
M. Grötschel and L. Lovász, Combinatorial optimization, Handbook of Combinatorics (R. Graham, M. Grötschel, and L. Lovász, eds.), North-Holland, Amsterdam, 1995, pp. 1541–1598.
P. Hall, On representatives of subsets, Journal of the London Mathematical Society 10 (1935), 26–30.
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.
S. Krogdahl, A combinatorial proof of lawler’s matroid intersection algorithm, unpublished manuscript (partly published in [14]) (1975).
E.L. Lawler, Combinatorial optimization: Networks and matroids, Holt, Rinehart and Winston, New York etc., 1976.
B. Spille, Primal characterizations of combinatorial optimization problems, PhD Thesis, University Magdeburg, Germany, 2001.
A.S. Schulz, R. Weismantel, and G.M. Ziegler, 0/1 integer programming: optimization and augmentation are equivalent, Algorithms-ESA95 (P. Spirakis, ed.), Lecture Notes in Computer Science 979, Springer, Berlin, 1995, pp. 473–483.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Firla, R.T., Spille, B., Weismantel, R. (2003). Algorithmic Characterization of Bipartite b-Matching and Matroid Intersection. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds) Combinatorial Optimization — Eureka, You Shrink!. Lecture Notes in Computer Science, vol 2570. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36478-1_7
Download citation
DOI: https://doi.org/10.1007/3-540-36478-1_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00580-3
Online ISBN: 978-3-540-36478-8
eBook Packages: Springer Book Archive