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.
> Engineers design materials, structures and systems while considering the limitations imposed by practicality, safety and cost.
That's where I begin to say that computing comes up short as 'engineering':
The problem is that too often in computing the "design" work, just the design work alone, before construction, cannot really tell what the "practicality, safety and cost" will be. So, too often in computing we have to build the system and then test it to know what its "practicality, safety and cost" are. That was often the situation in the construction of medieval cathedrals: Some examples stood; some fell down; some on the borderline got weaker over time. Apparently eventually the strong cathedrals were built mostly drawing from experience, that is, closely copying what had already worked before. That technique is trial and error and copying and not really the 'design' of engineering.
If bridge engineering were the same as software construction, then just to know how strong the bridge was we'd just have to build the bridge and then test it. For rocket engineering, to know if it could reach orbit we would have to build and launch it. Indeed, instead, in rocket engineering we can determine the rocket trajectory that will put the maximum payload into the desired orbit.
> 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.
For computing being 'engineering', that is an old sore point with me. I believe that computing should be engineering but so far really misses some key points.
Here, close to the article, is an example of some of what is missing:
In engineering for, say, a bridge, the design engineer can get quite comprehensive data on the 'engineering properties' of the materials, components, and processes he is intending to use. E.g., he knows the stiffness of steel beams, the tensile strength of steel cables. and how much weight a reinforced concrete column can carry.
Now in computing, for an algorithm, what do I know about the resources it requires? E.g., I just wrote a Web site session state store using TCP/IP for communications, my own code to convert the TCP/IP streams to the 'messages' I needed, and Microsoft's .NET collection class SortedDictionary to store the pairs of session keys and session values. So, how do I know fast my code will be and how much storage it will need? That is, could I get data on TCP/IP and SortedDictionary so that I could tell before writing and running the code?
That is, do I have solid engineering information about the components I used that will let me know, before writing and running the code, the final performance of my software?
NO!!!
Instead, about all I can do is run the code and measure the execution time. For the storage needed, I don't have a good solution even given the running code.
So, by analogy, if bridge building was like software writing, then a bridge engineer would not know how strong his bridge was until he built it and tested it with loads.
So, net, the bridge designer can 'engineer' his bridge just on paper before any construction has started, but I can't do the same for my session state store.
Again, a big difference is that the bridge engineer has detailed engineering information on his components and I do not.
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.