Network Algorithms: Scheduling and 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.