Research Initiation Award: Network Optimization: Flows, Cuts and Scheduling

大型网络是现代全球基础设施的重要组成部分。 必须以尽可能有效的方式使用和管理这些网络。 这个项目集中在网络优化中的两个基本问题：（1）计算流和切割，以及（2）在处理器网络上调度进程。 我们的目标是设计有效的算法，顺序和并行，在这些领域的一系列问题。 流量和切割问题包括最大流量、多商品流量和最小切割。 这项工作的基本网络算法的应用范围从切割平面算法旅行商问题的VLSI设计问题稀疏矩阵问题。 调度工作分析的问题，调度进程的网络上的处理器和开发的算法，以帮助决定是否应在本地处理或通过网络发送到远程处理器的工作。 通过理解在各种并行机器和机器网络上调度的复杂性，可以更好地利用当前的计算机，并且可以基于在该机器上调度的难度来设计未来的计算机。 这项工作将有一个重要的实验组成部分，利用访问DECmpp 12000与2K处理器。

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.