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.