Some references point to Bellman's The Art of Dynamic Programming, but after a quick look, the book, under "Bottleneck problems", does not seem to contain an explicit solution description as can be commonly seen in research papers or course material (such as the Introduction to Algorithms by Cormen, Rivest, Leiserson and Stein) on the subject, unless I overlooked a few important equations.
Dear Philon Nguyen, A complete chapter is available at link below.
http://www.cs.berkeley.edu/~vazirani/algorithms/chap8.pdf
@Afaq Ahmad: thank you for the link... My question was more historical than technical... I was interested in knowing who first came up with a description of the algorithm in a textbook or a book... I found somewhere that somebody referred to Bellman, but Bellman does not give an explicit description of the algorithm after a first quick glance (but I didn't try yet to link his differential equation notation to the one's we conventionally see in textbooks such as the one you linked)...
Has the algorithm become somewhat folklore? Most of us can remember that Quick Sort was first published by Hoare. Some of us were told that Merge Sort was a Von Neumann trick... We sometimes link binary systems to p-adic systems, at least in the Western canon...
To be honest, I wouldn't even be surprised if the algorithm could be traced back to Ancient Japan, China or India... due to its "abacus" nature...
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms