Kolla Receives NSF CAREER Award to Investigate NP-Hard Problems

CS Assistant Professor Alexandra Kolla recently received a prestigious young faculty NSF CAREER award to better understand the limitations of approximation algorithms for solving combinatorial optimization problems. Also known as NP-hard, these types of problems are nearly impossible to solve quickly.

Alexandra Kolla

An example of an NP-hard problem is figuring out the shortest route for a package delivery driver that visits all homes within an area exactly once and returns to the starting point. According to Kolla, one could write an algorithm to solve this problem quickly if there were only 10 homes on the route by brute-forcing all possible routes. “However, when the number of inputs is large, it would take a lifetime to come up with the best possible path,” she said

Because finding a solution with a fast runtime is critical, computer scientists do the next best thing: they write an algorithm that can be executed quickly by approximating the best solution. “Maybe you can’t have the shortest route between all the homes, but if the solution is within a factor of two or three, then you’re happy,” Kolla said.

In practice, approximation algorithms are used to address complex issues like semiconductor chip design, airline scheduling, as well as package delivery—among other things. But how can one know when such an algorithm has reached its best approximate solution?

Kolla aims to address that question with her CAREER-funded research by developing algorithms to disprove the Unique Games Conjecture (UGC), which, if correct, states that many of the problems people would most like to solve are not only NP-hard, but finding even a good approximation of the solution is impossible regardless of the computing power.

“We’ve come close to disproving [UGC] for a large class of problems, but there are still some cases left,” she said. “With this project, we’ll be attacking a large group of those cases to disprove the conjecture.”

A second aim of the project is to design algorithms for a specific class of NP-hard problems that include all but the worst-case instances, or graphs. “I propose to model the graphs that come up in practice most often, and I’ll design algorithms for problems that only work on those graphs with high probability,” Kolla said. “That means my algorithms would solve the problems of interest most likely.”