The project studies combinatorial optimization, with emphasis on problems related to commodity flow and minimum-ratio cuts. Deeper understanding of the combinatorial structure of these problems will result in improved algorithms for a variety of applications, including graph bisection, small area VLSI layout, scheduling, and routing. All of the currently known algorithms for finding exact solutions to multicommodity flow are very slow. These algorithms are based on general linear programming (LP) techniques and do not take advantage of the underlying combinatorial structure of the problem. Applying general LP techniques to solving such problems leads to even slower algorithms. The main goal of this project is to find alternative approaches to solving multicommodity flow and related problems. The goal is to improve both sequential and parallel complexity. In many applications, solving a multicommodity flow is only a first step in approximately solving an NP-complete problem; in the majority of such cases there is no need to have an exact solution of the multicommodity flow problem. One of the focuses of the project is to develop the design of efficient approximation algorithms. Another natural application of the multicommodity flow methods is in the area of routing in distributed communication networks. For example, problems related to managing available bandwidth can be stated as variants of multicommodity flow, where the information rate corresponds to flow and the bandwidth of every link corresponds to its capacity. The distributed, real-time nature of communication networks presents several challenging obstacles that do not exist in an off-line, sequential setting. Among them is the fact that not all the information is known in advance, which means that the algorithms have to work on-line. Second, there is usually no `manager` node that has a complete information about the network and that makes all the decisions. Therefore, the algorithms should work with partial information.
