[oxavier]

> Moreover, well-known algorithms for linear programming like simplex and primal-dual methods have straightforward (and illuminating!) combinatorial interpretations when restricted to minimum-weight bipartite matching.

I you have any resource illustrating this point, please share. I would be very interested.

I liked this video [0] about how the Hungarian Algorithm is a particular case of the primal-dual method and I am eager to dig further.

[0] https://www.youtube.com/watch?v=T4TrFA39AJU

[tmyklebu]

This was a popular topic in '80s linear programming books. Chvatal's "Linear programming," for instance, is carefully-written and devotes about 100 pages devoted to network simplex. Papadimitriou and Stieglitz's "Combinatorial optimization: algorithms and complexity" explicitly goes through primal-dual derivations of algorithms for shortest path, max flow, and min-cost flow (including bipartite matching). I haven't read it in any detail, but https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf is online and might be to your liking.

[oxavier]

Many thanks!