Part I

"Anyway, who is claiming anything for their own?"

From CLRS and much more, it is fully fair to say that CS is "claiming" that linear programming (LP) is part of CS.

Beyond what I've mentioned so far about LP in CLRS, there is a much bigger reason to claim that CS is "claiming" LP: The history is that operations research wrestled with integer LP (ILP). There is a claim that for a while G. Dantzig, the inventor of the simplex algorithm, looked at ILP and guessed that he would be able to modify the simplex algorithm to handle integers easily. Of course, decades later, no one has!

So, slowly the image appeared: In worst case, for exactly optimal solutions, the ILP algorithms had running time exponential in the size of the input data. So, they were like total enumeration. Bummer. So, then, asymptotically, polynomial would be faster, and Jack Edmonds said that a 'good' algorithm had polynomial running time in the worst case.

Klee and Minty showed that with one of the most popular pivot rules, simplex had exponential running time; the assumption has been that with any pivot rule, simplex is exponential.

Practice showed that with the usual practical problems on an LP with m constraints, the running time was about 3m iterations and, thus, polynomial on average.

K. Borgward did some 'random geometry' and showed that on average simplex would have polynomial running time, explaining the 3m performance.

Eventually Shor, Khachiyan, etc. showed a polynomial algorithm for linear programming based on cutting planes for ellipsoids. Alas, apparently whenever the polynomial algorithm was faster than simplex, both ran too long to be practical!

So, for the first test of the importance of polynomial algorithms, the effort fell face down in the mud: Simplex is exponential worst case and polynomial average case, and the polynomial algorithms are essentially never faster in a practical way!

So, dear Bell Labs was working on designing communications networks, discovered the role of ILP, encountered the worst case exponential execution time, and got with the theory of NP-completeness and wrote:

Michael R. Garey and David S. Johnson, 'Computers and Intractability: A Guide to the Theory of NP-Completeness', ISBN 0-7167-1045-5, W. H. Freeman, San Francisco, 1979.

Here can see the role of the 'satisfiability' (SAT) problem -- it is in NP-complete.

Presto! CS, long interested in 'computational complexity', especially running time, and, of course, regarding SAT as part of both EE and CS but not really operations research or optimization, takes NP-completeness as its own!

In money, students, profs, department sizes, headlines, etc., poor, little operations research, optimization, and even all of applied math can't compete with CS. So, CS grabs LP, ILP, network flows, NP-completeness, etc. along with SAT!

Okay, CS, it you are going to hijack all of 'combinatorial optimization', then realize that progress will require some good math research, and step up to the math.

Now back to this thread: So far, as in CLRS, CS is having trouble even writing with high quality about the simplex algorithm. So, putting combinatorial optimization and NP-completeness in the butter finger, dirty fingernails, unwashed hands of CS is a bad move for the future.

That's some of the larger story about the significance of CS hijacking topics from applied math.

Am I torqued? Sure: CS grabs the ball, claims to want to run with it, and then falls into the mud. I'm calling them out on it. It needs to be done.

"Throw me the ball! Throw it to me! I can score .... Splat." CS, even at MIT, too often can't even write with high quality about the simplex algorithm. REALLY big BUMMER.

Just like on a ball team, just ain't throwing CS the ball anymore. Again, they need to clean up their act in math. As CS hijacks LP, simplex, ILP, network flows, combinatorial optimization, and NP-completeness, they are getting into some of the hardest math research in all of history. For that they will need to be good at, would you believe, a junior level ugrad course in LP, and even there, even the MIT profs, need to 'pull up their grade'.

There's a war story: In some parts of 'enterprise software', a user gets to enter 'constraints'. E.g., let's figure out what we are going to do in the factory today. We know that want all the trucks loaded by 5 PM. Want all the painting done by noon so that it can be dry by 3 PM in time to be packed. Only have 2000 gallons of paint so whatever we do today has to use no more than the 2000 gallons. Etc. So, not really optimizing but are just 'satisfying'.

So, seeing this enterprise software problem, CS started the field of 'constraint logic programming'. Great! Hot new field! Charging forward!

Only a few weeks later, CS discovered that writing software to take just any collection of constraints and satisfy all of them is not so easy. I mean, even permitting using things as awesomely powerful as neural nets, AI, and, even, genetic programming, it wasn't so easy!

A few weeks after that they discovered that even if all the constraints are linear, it's not so easy! Soon they learned a lesson from operations research: They were looking for a feasible solution to an LP, and generally finding if there is a feasible solution is about the same 'difficulty' as finding an optimal solution. So, really, the linear 'constraint satisfaction' problem is not much different than just LP. Sorry guys. Better luck next time. Pick yourselves out of the mud and hit the showers.

So, SAP got interested in a French company that was interested in R. Bixby's LP software C-PLEX.

And the hot, new CS field of 'constraint logic programming' got to look a bit silly. Splat.

On my research paper, grow up! We're talking adult level activity here! No longer is it fair to plead that haven't covered that material yet! Instead, the goal is progress in research. If start with a computing problem, then the research is 'CS'. We do the research the best way we can. If we have a powerful, clean, rock solid solution with some new math theorems and proofs, then okay. So be it. That's just part of 'research'. If CS doesn't yet know this material, then maybe they will have to learn it.

Parts of academic finance learned about stochastic integration. Parts of mathematical physics learned about that math also along with Riemannian geometry and Hilbert space theory. Parts of chemistry learned about group representation theory. Parts of chemical engineering learned about ILP and dynamic programming.

Actually, reviewing my paper was not so difficult: I suspect that the editor in chief walked the paper to the math department, found a good probabilist, and got told "The math looks fine; I don't know what it means for CS.". Then he walked to the CS department, found an appropriate guy, and got told "It looks good for CS, but I can't say if the math is correct.". Done. How hard is that?

Grow up: The math is fair game. Not only that, the math is the main tool for the future of CS. If you didn't realize that, then you can say that you learned it first here. I can understand why one wouldn't get this lesson from CLRS!

Net big picture: Math is by a wide margin the oldest, deepest, most solid, most powerful, and most general subject in all of academics. Moreover, nearly uniformly, in all fields, the best progress is from 'mathematization' of the field. Get used to it! For CS, do the math. For the applications to computing, do that in the footnotes or the exercises!