CCF-BSF: AF: Small: New Randomized Approaches in Approximation Algorithms

Georgia Tech Research Corporation, Atlanta GA

Investigators

Abstract

In the modern world, many industries make every day crucial decisions by solving large scale discrete optimization problems including routing of delivery trucks, designing schedule of airplanes, and deciding on the logistics of inventory supplies. Unfortunately, many of these problems are computationally hard to solve exactly. The area of approximation algorithms has grown as a general theory to develop and analyze solutions that can be efficiently computed as well as give near-optimal solutions. One of the most successful approaches in this area has been to: (1) formulate the problem at hand using an easily solvable continuous mathematical characterization; and (2) applying a rounding method that converts the solution to the continuous characterization into a discrete feasible solution to the original problem. This project aims to develop a new generic and broadly applicable rounding method based on probabilistic tools. The success of the project will help obtain new and improved solution methods to many fundamental discrete optimization problems. The PIs of this collaborative NSF-BSF project compose a harmonious team as both PIs have complementary proficiencies in algorithmic research. This will contribute to achieving one of the primary goals of this project, which is to extend and maintain the US-Israeli scientific collaboration between the PIs. Another paramount goal of this research project is to include students, both undergraduate and graduate, as full active participants. A special emphasis will be given to students coming from under-represented groups. The PIs plan to assist the dissemination of knowledge by integrating results from this research into inter-disciplinary curriculum activities at all levels, spanning computer science, applied mathematics and operations research. The project aims to enrich the algorithmic toolkit in the area of approximation algorithms and show that a new approach based on discretized Brownian motion is applicable to a wide range of NP-hard problems. A special emphasis is given on optimization problems that are considered fundamental including traveling salesman problem, maximum cut and maximum satisfiability. Any new insight into the solution of fundamental problems, such as the ones mentioned above, is likely to have much wider implications as these problems form basic building blocks for numerous discrete optimization problems occurring in both theory and practice. Thus, this project also aims to study the applicability of the newly developed technique to such problems.