|
|
|
J. Edmonds determined a totally dual integral linear system whose solution set is the convex hull of common bases of two matroids on S. He obtained this way a min-max formula for the maximum weight of a common basis which uses dual variables assigned to subsets of S. A more concise min-max theorem, based on weight-splittings and avoiding those dual variables, was derived in [5]. Here we exhibit a short direct proof of this result, taken from an expository paper written in Hungarian, that can be interpreted as a straight extension of Egerváry's original proof for his min-max theorem on the maximum weight of perfect matchings in a bipartite graph.
Bibtex entry:
| AUTHOR | = | {Frank, Andr{\'a}s}, |
| TITLE | = | {A quick proof for the matroid intersection weight-splitting theorem}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2008}, |
| NUMBER | = | {QP-2008-03} |