I wonder why most of those graph/network flow algorithms we learnt (Dijkstra, Bellman-Ford, Ford-Fulkerson, etc.) were not published/well-known until 1950s while the history of graph theory can be traced back to Euler's time? Nobody was interested in those particular problems or there was no serious applications before computers were invented?
The problems were probably too complex to solve by hand. That would be my guess. These networks can be incomprehensibly big. There were giant networks before computers, such as telegraphs or pipes. Those don't have any real control over the way the flow works though. A little bit but no where as much as a computer network does.
I agree with Ollie's surprise about these problems having such a short history. I was able to quickly find a couple of references to Network Flow and the more general (but harder to solve) Linear Programming problem, dating back to 1930's Russia.
My take is that, prior to the development of Computer Science as a discipline, there was relatively little focus by mathematicians on algorithmic efficiency. Much more effort was devoted to questions of what is, or is not, possible or solvable. On the other hand, the people best equipped to develop algorithms, were mathematicians.
Also, for small networks, it is fairly easy to come to an optimal, or nearly optimal, solution by just greedily sending more flow along augmenting paths. This is such a simple idea, that there may not have been widespread awareness that this problem was important and unsolved.
If anyone finds a reference to historical info before 1930, I would be interested. Links: homepages.cwi.nl/~lex/files/histtrpclean.pdf http://en.wikipedia.org/wiki/Linear_programming#History
I am fairly sure I remember reading something about people earlier using networks of waterpipes to "physically solve" network routing problems for more abstract kinds of flows, but I wasn't able to find a reference.
This is an off-topic question.
ReplyDeleteI wonder why most of those graph/network flow algorithms we learnt (Dijkstra, Bellman-Ford, Ford-Fulkerson, etc.) were not published/well-known until 1950s while the history of graph theory can be traced back to Euler's time? Nobody was interested in those particular problems or there was no serious applications before computers were invented?
The problems were probably too complex to solve by hand. That would be my guess. These networks can be incomprehensibly big. There were giant networks before computers, such as telegraphs or pipes. Those don't have any real control over the way the flow works though. A little bit but no where as much as a computer network does.
DeleteI agree with Ollie's surprise about these problems having such a short history. I was able to quickly find a couple of references to Network Flow and the more general (but harder to solve) Linear Programming problem, dating back to 1930's Russia.
ReplyDeleteMy take is that, prior to the development of Computer Science as a discipline, there was relatively little focus by mathematicians on algorithmic efficiency. Much more effort was devoted to questions of what is, or is not, possible or solvable. On the other hand, the people best equipped to develop algorithms, were mathematicians.
Also, for small networks, it is fairly easy to come to an optimal, or nearly optimal, solution by just greedily sending more flow along augmenting paths. This is such a simple idea, that there may not have been widespread awareness that this problem was important and unsolved.
If anyone finds a reference to historical info before 1930, I would be interested.
Links:
homepages.cwi.nl/~lex/files/histtrpclean.pdf
http://en.wikipedia.org/wiki/Linear_programming#History
I am fairly sure I remember reading something about people earlier using networks of waterpipes to "physically solve" network routing problems for more abstract kinds of flows, but I wasn't able to find a reference.