An experimental study will be performed to investigate algorithms for problems concerned with computation of network flows, including the minimum cost flow problem and possibly restrictions such as the maximum flow problem, the shortest path problem, or the assignment problem. The experimental study will proceed as a cooperative competition among members of the research community. Participants will submit code for evaluation or will perform specific experiments at their home sites. The competition will culminate in a workshop where participants will describe their results; the best implementations for several input classes and computing environments will be identified. Competitors will generate a large amount of data about the performance of these algorithms. Parametric and nonparametric methods of data analysis will be applied to obtain quantitative descriptions of performance as a function of input parameters. Some particular results to be obtained include: analysis of the relationship between running time and standard combinatorial measures of performance; identification of input properties that are "hard" for certain algorithms; and development of realistic random models of networks. Besides providing substantial new knowledge about the performance of these algorithms, the project will also give insight into experimental methods for algorithm analysis and into the viability of using computer research networks in such cooperative projects.
