News for hackers. Stuff that matters.
Re:Linear Programming: How Does It Work? by arghbleargh on Monday June 06, 2016 @04:31AM (#11845375)
There is a linear programming formulation of the shortest path problem: see https://en.m.wikipedia.org/wiki/Shortest_path_problem#Linear.... Indeed the vertices of the simplex method would correspond to paths, but I think running the simplex method on the dual formulation is more akin to Dijkstra's algorithm. Actually, I think the simplex method on the dual and Dijkstra's are equivalent, although I did not work through the details carefully.
Re:Linear Programming: How Does It Work? by mathgenius on Monday June 06, 2016 @11:24AM (#11847437)
Aha, yes, this is what I was looking for. Thankyou!

Reminds me also of using linear programming to do belief propagation and decode sparse codes.