Write a program to permute the columns of a square matrix so as to minimize the sum of elements on the main diagonal.
If we number the columns in this matrix from 0 through 4 and then rearrange them so that they appear in the order8 16 15 91 64 83 42 93 75 27 76 95 75 81 50 20 42 96 90 24 38 28 2 15 81
then we get the matrix2 1 4 0 3
The sum of the elements on the main diagonal of this matrix is15 16 64 8 91 93 42 27 83 75 75 95 50 76 81 96 42 24 20 90 2 28 81 38 15
and no other permutation of the columns can yield a lower sum.15 + 42 + 50 + 20 + 15 = 142
This problem is known as the assignment problem, and it arises in a great many industrial applications. For example, the columns might represent jobs and the rows might represent workers, with the matrix entry representing the number of hours it takes the corresponding worker to complete the job. The solution to the assignment problem tells us how to assign the workers to the jobs so as to minimize the total number of hours worked. In the example above, if we also label the rows from 0 to 4, then the given solution says that we should assign job 2 to worker 0, job 1 to worker 1, job 4 to worker 2, job 0 to worker 3, and job 3 to worker 4 to get a total minimum of 142 hours worked.
Input and Output format. Assume that the matrix is on standard input: the dimension N followed by N lines with N integers per line. You may assume that the entries are all between 0 and 999999. Print the permutation and the total cost. For N less than 25, also print the permuted output matrix.
Reduction. Your assignment is to solve this problem by reducing it to the mincost maxflow problem. You may use the code graph.h, edge.c, and graph.c, which comprise an implementation of the cycle-canceling algorithm from the book (Program 22.8). The implementation uses the Bellman-Ford algorithm to find negative cycles (Exercise 21.134). Do not modify this code at all: just write a client program that uses it. Following the vague description on page 462, your reduction will be like the one in Program 22.6 on page 421, but your code will be different because you are starting with a matrix, not a network, and because you are reducing to a flow network with costs.
Analysis. Once you get your program debugged and working for small N, run it for larger values of N, stopping when your runtime exceeds 1 minute. You can use the program generate.c to generate random matrices. Develop a formula that you can use to predict the running time of the program, as a function of N. Give both the exponent and constant in your formula.
Extra Credit. The assignment is an exercise in reduction and does not reflect the way assignment problems are solved in industrial applications, for two primary reasons. First, in real applications, the matrices involved are sparse: for example, each worker is likely to be qualified to do a few jobs, but not every job. Second, mincost-maxflow problems are so widely applicable that fast optimized solvers are widely available. Since the solvers are designed for sparse graphs, they use a sparse input format, such as a list of edges. Even so, we can go ahead and apply an industrial strength solver designed for sparse inputs to our dense input instances.
For extra credit, use the min cost flow solver. developed by Andrew Goldberg. Goldberg's implementation uses a sophisticated cost-scaling successive approximation algorithm for the min cost flow problem. Goldberg's algorithm uses the DIMACS file format, so you will need to translate our input format to DIMACS form. Run experiments and develop a formula that you can use to predict the running time of this solution, as a function of N.