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\u2019m still trying get people to do a good computer implementation. It\u2019s 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 \u201cPaths, Trees and Flowers\u201d 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 \u201cMaximum Matching and a Polyhedron with 0-1 Vertices\u201d 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\u2019s Gallery for his \u201cfundamental contributions in combinatorial optimization, discrete mathematics, and the theory of computing.\u201d
\u00a0
edmonds_goldman \u2013 slides<\/p>\n","protected":false},"excerpt":{"rendered":"
Title: Matroids and Optimum Branching SystemsAbstract: 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,…<\/p>\n","protected":false},"author":3,"featured_media":0,"template":"","meta":{"_acf_changed":false,"_relevanssi_hide_post":"","_relevanssi_hide_content":"","_relevanssi_pin_for_all":"","_relevanssi_pin_keywords":"","_relevanssi_unpin_keywords":"","_relevanssi_related_keywords":"","_relevanssi_related_include_ids":"","_relevanssi_related_exclude_ids":"","_relevanssi_related_no_append":"","_relevanssi_related_not_related":"","_relevanssi_related_posts":"","_relevanssi_noindex_reason":"","_tribe_events_status":"","_tribe_events_status_reason":"","footnotes":""},"tags":[],"tribe_events_cat":[],"class_list":["post-30556","tribe_events","type-tribe_events","status-publish","hentry"],"acf":[],"yoast_head":"\n