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

大型网络是现代全球基础设施的重要组成部分。以最有效的方式使用和管理这些网络至关重要。本项目重点研究网络优化中的两个基本问题：(1)计算流和切割，以及(2)处理器网络上的调度进程。目标是为这些领域的一系列问题设计有效的顺序和并行算法。流量和切割问题包括最大流量、多商品流量和最小切割。这项关于基本网络算法的工作具有广泛的应用，从旅行推销员问题的切割平面算法到VLSI设计问题再到稀疏矩阵问题。调度工作分析了在处理器网络上调度进程的问题，并开发了有助于决定作业是应该在本地处理还是通过网络发送到远程处理器的算法。通过了解各种并行机器和机器网络上调度的复杂性，可以更好地利用当前的计算机，并且可以根据该机器上调度的难度来设计未来的计算机。这项工作将有一个重要的实验组件，利用访问带有2K处理器的DECmpp 12000。

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.