News for hackers. Stuff that matters.
Re:Minimum bipartite matching via Riemann optimization by tmyklebu on Thursday January 09, 2025 @01:05PM (#42648225)
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.
Re:Minimum bipartite matching via Riemann optimization by oxavier on Thursday January 09, 2025 @10:58PM (#42652291)
Many thanks!