AF: Small: Faster and Better Algorithms for, and via, Mathematical Programming Relaxations

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

Optimization algorithms underpin fundamental advances in computer science, engineering and social sciences. As an example, the spectacular success of machine learning in the recent past is partly due to the important role of a class of continuous-optimization algorithms. In another direction there have been a number of breakthrough advances on fundamental and widely applicable problems for graphs and networks, such as the maximum-flow and minimum-cut problems, based on fruitful interactions between continuous optimization and discrete optimization. Increasing data-set sizes and new models of computation require further advances in optimization algorithms to reap the rewards of the data revolution. This proposal aims to develop faster approximation algorithms for a class of continuous-optimization problems and to leverage these algorithms to obtain faster approximation algorithms for several well-studied and applicable problems in discrete and combinatorial optimization. The project will support and train one PhD student in the design and analysis of algorithms at the University of Illinois at Urbana-Champaign. The investigator plans to write a survey on recent developments on fast approximation schemes for positive linear programming with an emphasis on applications to implicit programs that arise in combinatorial optimization. The investigator will continue to develop and teach a course on algorithms for big data at the University of Illinois and lecture notes and related material will be made publicly available. The technical focus of the project is to develop fast approximation algorithms via mathematical-programming relaxations for a number of fundamental problems in discrete optimization. This involves developing fast algorithms for solving the relaxation as well as fast algorithms for rounding. The interplay between discrete and continuous methods will be an important technical viewpoint. The project will have two thrusts. The first is to develop fast algorithms for solving positive linear programs and several concrete applications. A particular focus will be on implicit linear programs that arise in combinatorial optimization. The second thrust will be fast algorithms for the traveling salesperson problem (TSP) and related problems in both undirected and directed graphs. Applications to submodular objective functions will also be considered. 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.