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.

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