CAREER: Pursuing New Tools for Approximation Algorithms

University Of Washington, Seattle WA

Investigators

Abstract

Many of the large-scale industries are now employing sophisticated algorithms to solve variants of fundamental optimization problems. For example, Amazon uses a variant of the Traveling Salesman Problem (TSP) known as the vehicle routing problem for routing Amazon-Fresh Trucks. Uber solves a variant of TSP to route its shared-ride services. Many of the social networks including Facebook and Google+ solve variants of constraints satisfaction problems for their social targeting tasks. These optimization problems have ubiquitous applicability but they are computationally challenging in the sense that many are known to be NP-hard. This means that under standard assumptions they cannot be solved optimally by algorithms which terminate in reasonable time. The field of approximation algorithms attempts to develop efficient algorithms that find solutions close to the optimum. These approximation algorithms have found many applications in the real world. The project will advance state-of-the-art in approximation algorithms which will not only have impact on industry but also contribute to our fundamental understanding of P vs NP issue, which is at the core of computer science. This project aims to develop new tools and techniques to obtain improved approximation algorithms for fundamental optimization problems, including the TSP and Constraint Satisfaction problems. The project intends to prove new algebraic properties of stable polynomials and use them to study graphs from an algebraic point of view. These tools will lead to design a new class of approximation algorithms. These new tools coming out of this project will be incorporated in the next generation of courses in approximation algorithms that focus on algebraic techniques. Although grounded in computer science theory, the project will also attract many graduate students outside of theory from applied fields like machine learning and artificial intelligence forming basis for interdisciplinary research.