"Underlying our approach to this subject is our conviction that 'computer science' is not a science and that its significance has little to do with computers. The computer revolution is a revolution in the way we think and in the way we express what we think. The essence of this change is the emergence of what might best be called procedural epistemology the study of the structure of knowledge from an imperative point of view, as opposed to the more declarative point of view taken by classical mathematical subjects. Mathematics provides a framework for dealing precisely with notions of 'what is.' Computation provides a framework for dealing precisely with notions of 'how to.'"
> Mathematics provides a framework for dealing precisely with notions of 'what is.' Computation provides a framework for dealing precisely with notions of 'how to.'"
But some parts of math deal "with notions of 'how to'" and there commonly do so more "precisely" than computer science. There are such parts in optimization, control theory, statistics, and numerical analysis.
E.g., numerical analysis says how to (1) solve systems of linear equations numerically exactly using just single precision arithmetic, (2) solve systems of linear equations with accuracy guaranteed by error bounds from condition number, (3) solve systems of large, sparse linear equations where the matrix is large, positive definite, and diagonally dominate, (4) how to solve ordinary differential equation initial value problems, e.g., for space flight trajectories, and (5) how to solve partial differential equations of heat flow, fluid flow, and electromagnetic fields, and (6) how to do discrete Fourier transforms of positive integer n points in time proportional to n log(n) instead of n^2; statistics says how (1) to get minimum sufficient statistics in the Gaussian case, (2) how to design a most powerful statistical hypothesis test, (3) how to pick a survey sample size that will give desired accuracy, (4) how to get minimum variance, unbiased estimators in multivariate statistics, and (5) at a Web site with users arriving at a rate of 10 a second, how to find the probability of a minute with arrival rate of over 20 a second; control theory can show (1) how to execute best possible decision making over time under uncertainty, (2) how a rocket can reach orbit for minimum fuel, (3) how an airplane can climb to a given altitude in least time; and optimization can show (1) how to find least cost flows on large networks while avoiding cycling in the network simplex algorithm, (2) how to assign interceptors to targets in the best possible way in guaranteed execution time, and (3) how to assign signals to satellite channels to minimize the worst case of signal interference.
Do you have a reference for "(2) how to assign interceptors to targets in the best possible way in guaranteed execution time"? I would love to read that paper!
The specific problem is a special case of the 'assignment' problem. First cut, it looks like 0-1 integer linear programming and, thus, maybe in NP-complete.
Looked again, the problem is least cost network flows. That is a linear programming problem. In that problem, if the arc capacities are integers, and in this practical problem they are, then the simplex algorithm can easily start with a basic, feasible, integer solution, and the simplex iterations will automatically maintain an integer solution and, then, find an optimal integer solution which provides the optimal assignments.
When we apply the simplex algorithm to least cost network flows, we get to take advantage of the fact that the problem is not fully general linear programming, and the advantage we can take is huge. E.g., the arcs of a basic, feasible solution form just a spanning tree in the network; the 'entering variable' in the simplex algorithm just adds an arc to the spanning tree and, thus, yields a circuit; we run flow around the circuit in the direction that makes money until the flow on some arc is zero and that arc determines the 'leaving variable'. Using the 'strongly feasible' basis ideas of W. Cunningham, long at Waterloo, we can avoid cycling.
But, the simplex algorithm for least cost network flows, as far as I know, is not guaranteed, worst case polynomial.
However, read:
Dimitri P. Bertsekas, 'Linear Network Optimization: Algorithms and Codes', ISBN 0-262-02334-2, MIT Press, Cambridge, MA, 1991.
and in there, or elsewhere in Bertsekas's work, is an algorithm for least cost network flows and that is worst case polynomial.
Done.
And I covered nothing classified!
And for this thread, we have a "how to" with high precision from some applied math.
-- Preface to the First Edition of Structure and Interpretation of Computer Programs (http://mitpress.mit.edu/sicp/front/node3.html)