Simplex method was a game changer.<p>Its a funny algorithm: worst-case time complexity is exponential in the input size, and is pretty easy to demonstrate (see "Klee-Minty cube" on Wikipedia). It has a couple of "rules" you can change out that will fix the exponential problem for some cases, only to introduce new problematic cases elsewhere. However the reality is that it demonstrates polynomial-like performance on almost all problems of interest, and that is why it is so widely used.<p>Later, interior point methods arose that can be faster sometimes (and are polynomial time complexity), but they didn't kill the simplex method. This is partly due to one key property of the simplex method: at optimality, you can change the linear program in many different small ways and start the algorithm again from where you left off (sometimes you need the dual simplex method, a sibling method). You'll return to feasible optimality in usually only a few iterations. This is what powers the branch-and-bound approach to integer programming, which is the really useful application of LP these days. Interior point methods don't really have good warm starts to this day, certainly not good enough for branch-and-bound.<p>I've met several professors who kinda don't like the simplex method because (they say) it is not a beautiful algorithm from a theory perspective, but I think its wonderful.<p>Oh, and PSA: very difficult to implement correctly! The textbook algorithm will fail terribly on real problems due to floating point issues - please use an existing implementation if you need to solve LPs!
"The Lady Tasting Tea"[1] is a fantastic book about statisticians. Someone recommended that book to me as an intro to stats, which it most certainly is not. However, if you have had even a single course in statistics, you will recognize many of the names and learn how they influenced the modern era.<p>Frankly, I wish the author had devoted a couple of pages at the end of each chapter to delve deeper into the technical concepts. Nonetheless, the book makes an interesting read, even for non-statisticians.<p>[1]<a href="http://www.amazon.com/The-Lady-Tasting-Tea-Revolutionized/dp/0805071342" rel="nofollow">http://www.amazon.com/The-Lady-Tasting-Tea-Revolutionized/dp...</a>