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.