News for hackers. Stuff that matters.
Re:Advanced Data Structures by graycat on Friday November 04, 2016 @05:14PM (#12876177)
Thanks.

Given a directed graph with on each arc a maximum flow and a cost per unit of flow, how to find the least cost flows for a given total flow? That is linear programming. The simplex algorithm takes on a special form, and a simplex basic solution corresponds to a spanning tree. A simplex pivot is adding an arc to the tree to yield a circuit, and getting the cost of sending a unit of flow around the circuit evaluates that new arc. Etc.

W. Cunningham defined a strongly feasible basic solution which avoids cycling.

IIRC, D. Bertsekas has a good (polynomial) algorithm for that problem.

I didn't see such mentioned in your table of contents.

On my 14" screen, your PDF files would be much easier to read if the maximum number of characters per line was about 50.

There are no comments on this comment yet.