[dvse]

I think now it is fairly generally appreciated that interior point methods constitute perhaps the most powerful class of tractable algorithms there is, yet remarkably they are hardly ever mentioned in any of the undergrad CS algorithms classes. Usually there is a passing mention of linear programming to establish an auxiliary result like max flow / min cut duality but that's it.

[eshvk]

Yeah but an undergrad class in algorithms is supposed to in most cases just give you a deeper view of traditional C.S algorithms. There are quite a few topics which are barely skimmed ( approximation algorithms, randomized algorithms). I believe that is OK because as long as most of the students are trained to think algorithmically, that should be fine. After all, most advanced stuff becomes much easier once you have the basics fundamentals clear.

[dvse]

All true, but the idea that a good fraction of combinatorial algorithms that undergrads see can be replaced (albeit less efficiently) by linear programming is important. Not clear how classical CS curriculum helps to appreciate this either. And after all, LP used to be considered an almost elementary topic before it mysteriously dropped out the curriculum (perhaps something to do with linear algebra no longer being compulsory).