4 ms·

No cuts are necessary for minimum-weight bipartite matching as the constraint matrix is totally unimodular. Total unimodularity guarantees that any optimal bas

• whatever1 2y ago
  Spot on! I was just thinking about the case of having also complicating constraints. In the vanilla case is exactly as you say.
• oxavier 2y ago
  > 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 https://www.youtube.com/watch?v=T4TrFA39AJU
  • tmyklebu 2y ago
    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 https://math.mit.edu/~goemans/PAPERS/book-ch4.pdf is online and might be to your liking.
    • oxavier 2y ago
      Many thanks!