This project studies fundamental network problems, including maximum, minimum-cost, and multicommodity flow problems, shortest paths problems, minimum cut problems, and the assignment problem. These are classical combinatorial optimization problems that have numerous applications. Designing efficient algorithms and understanding combinatorial structure of these problems is important from a theoretical point of view because these problems are very basic to the field, and from a practical point of view because instances of these problems need to be solved. There is interest in extending the results of this work to related problems, such as linear programming. The research has three interrelated components: (1) the first involves a better understanding of combinatorial structure of these problems; (2) the second involves development of new algorithms that improve currently known bounds on the problem complexity; and (3) the third involves experimental evaluation of the currently existing and newly developed algorithms. The worst-case theoretical efficiency does not always correspond to practical efficiency. Experimental evaluation of existing and newly developed algorithms for some of the problems is of interest. The experimental research also motivates theoretical research by identifying subproblems and data structures needed by the implementations and by suggesting variations of algorithms which may be more efficient than the original variants originating in theoretical research.
