CAREER: Improved Approximation Algorithms for Graph Problems

Graphs are used to model transportation networks, social networks, the internet, and many other systems of major significance. A number of important computational problems naturally arise on these graphs. For example, one may wish to find the shortest route visiting all points – in other words, to solve the traveling salesperson problem.

Unfortunately, this problem and many others like it are believed to be computationally intractable, requiring lifetimes of computation to solve exactly. However, in many cases, it is computationally tractable to find an approximate solution, such that the cost of the proposed solution is guaranteed to be not much worse than the best cost achievable.

The guarantee is usually that the ratio of the cost of the generated solution to the cost of the best solution is at most some quantity, called the approximation factor. This proposal aims to find fast algorithms with low approximation factors, obtaining high-quality approximate solutions to such problems. The project also aims to broaden participation in mathematics and computing via undergraduate research, an educational website, and an interdisciplinary course.

More specifically, the goal of this research is to develop new tools for approximating NP-hard graph problems and to improve our understanding of powerful techniques such as max entropy sampling and iterative rounding. Through studying these methods, this project will deepen the connections between approximation algorithms and other areas of computer science and math like graph theory, graph sparsification, and the geometry of polynomials.

To pursue these goals, the investigator will focus on finding better approximation algorithms for several time-tested, fundamental graph problems including the traveling salesperson problem, its asymmetric variant, and a generalization of the minimum spanning tree problem known as k-edge-connected spanning subgraph (k-ECSS). All the problems considered are related to long-standing conjectures in mathematics and combinatorial optimization which will be examined alongside the algorithmic questions.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.