Network Algorithms: Scheduling and Routing

网络算法：调度和路由

• 批准号: 0105533
• 负责人: Satish Rao
• 金额: $ 20.21万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2004-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0105533&HistoricalAwards=false
• 关键词: Network; Algorithms; Scheduling; Routing

This research involves two applications of graph algorithms; the firstregards communication in networks, the second involves solving flowproblems in structured networks. The investigators study algorithmsfor finding paths connecting many communicating parties in a network.The goal is that the paths do not overutilize any particular link inthe network. The second item the investigators will study isthe famous problem of routing the maximum amount of flow througha network. This problem is itself interesting and has numerousapplications in fields as diverse as transportation and computer vision.More specifically, the investigaters study low congestion routing innetworks. This problem is easy in a relaxed fractional setting butnotoriously difficult in an integral setting. Recent work hasestablished relationships between a cut based upper bound and thefractional lower bound on this problem. These results will lead tobetter understanding of the integral version of this problem.Research on this problem has made use of techniques from linearprogramming, randomized rounding, combinatorial graph theory, as wellas geometric embeddings of graph metrics. For the maximum flowproblem, the investigaters study ideas in a recent maximum flowalgorithm in order to extend them to the minimum cost flow problem.The investigators also study the maximum flow problems on planar andother restricted classes of graphs.

本研究涉及图算法的两个应用；第一个涉及网络中的通信，第二个涉及解决结构化网络中的流问题。 研究人员研究了用于查找连接网络中许多通信方的路径的算法。目标是路径不会过度利用网络中的任何特定链路。 研究人员要研究的第二个项目是通过网络路由最大流量的著名问题。这个问题本身很有趣，并且在交通和计算机视觉等不同领域有广泛的应用。更具体地说，研究人员研究网络中的低拥塞路由。 这个问题在宽松的分数设置中很容易，但在积分设置中却非常困难。 最近的工作已经在这个问题上建立了基于切割的上限和分数下限之间的关系。 这些结果将有助于更好地理解该问题的积分版本。对该问题的研究利用了线性规划、随机舍入、组合图论以及图度量的几何嵌入等技术。对于最大流问题，研究人员研究了最近的最大流算法中的思想，以便将其扩展到最小成本流问题。研究人员还研究了平面和其他限制类图上的最大流问题。