Algorithms for Some Network Design Problems

PI将研究一些网络设计问题的近似和精确解的实用算法，例如寻找最低成本。在所有节点之间提供k-连通性的加权图的生成子图。PI还将研究稀疏证书在匹配和最大流量问题中的使用。我们的目标是使用稀疏证书来修剪掉不能产生最优解的边子集，从而减少所处理的图的大小。

The PI will study practical algorithms for approximation and exact solutions of some network design problems such as finding a lowest cost. spanning subgraph of a weighted graph that provides k-connectivity between all nodes. The PI will also investigate the use of sparse certificates in the context of matching and maximum flow problems. The goal is to use sparse certificates for pruning away a subset of the edges that do not contribute to optimal solutions, thus reducing the size of the graph that is processed.