Title: Matroids and Optimum Branching Systems
Abstract: The Optimum Branching Systems problem (OBS) is Given a directed graph G, specified root nodes r(i), and a cost for each edge of G, find a least cost collection of edge-disjoint directed spanning trees in G, rooted respectively at the nodes r(i), i.e., r(i)-branchings in G. We describe a polynomial time algorithm for OBS. The mincost network flow problem is a special case of OBS. However OBS does not reduce to it. By letting M1 and M2 be certain matroids, matroid intersection solves OBS, and a bunch of other combinatorial optimization problems. Matroid intersection is the only approach known for solving OBS. Curiously, the simplest way known to describe an algorithm for OBS is by matroid intersection for general matroids. Matroid algorithms use subroutine sources of the matroids, M, which say when a set is independent in M. The ingredients for solving OBS are in books on combinatorial optimization, but I’m still trying get people to do a good computer implementation. It’s clearly possible, but a bit complicated.
Bio: Jack Edmonds is a John von Neumann Theory Prize recipient and one of the creators of the field of combinatorial optimization and polyhedral combinatorics. His 1965 paper “Paths, Trees and Flowers” was one of the first papers to suggest the possibility of establishing a mathematical theory of efficient combinatorial algorithms. In that paper and in the subsequent paper “Maximum Matching and a Polyhedron with 0-1 Vertices” Edmonds gave remarkable polynomial-time algorithms for the construction of maximum matchings. Even more importantly these papers showed how a good characterization of the polyhedron associated with a combinatorial optimization problem could lead, via the duality theory of linear programming, to the construction of an efficient algorithm for the solution of that problem. In 2014 he was honored as a Distinguished Scientist and inducted into the National Institute of Standards and Technology’s Gallery for his “fundamental contributions in combinatorial optimization, discrete mathematics, and the theory of computing.”
edmonds_goldman – slides