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.
