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.