Large networks form an essential part of the modern global infrastructure. It is essential to use and manage these networks in the most efficient way possible. This project focuses on two fundamental problems in network optimization: (1) computing flows and cuts, and (2) scheduling processes on a network of processors. The goal is to design efficient algorithms, both sequential and parallel, for a range of problems in these fields. The flow and cut problems include maximum flows, multicommodity flows and minimum cuts. This work on basic network algorithms has applications ranging from cutting plane algorithms for traveling salesman problems to VLSI design problems to sparse matrix problems. The scheduling work analyzes problems of scheduling processes on a network of processors and develops algorithms that help to decide whether jobs should be processed locally or sent over the network to a remote processor. By understanding the complexity of scheduling on various parallel machines and networks of machines, current computers can be better utilized and future computers can be designed based on the difficulty of scheduling on that machine. The work will have a significant experimental component, taking advantage of access to a DECmpp 12000 with 2K processors.
