AF : Small : Fast algorithms for LPs, TSP, and Connectivity

Purdue University, West Lafayette IN

Investigators

Abstract

The field of theoretical algorithms has long emphasized the difference between polynomial and exponential running times, which has formed a sound theoretical basis for computation as a science and has also been robust to many technological advancements. Recent computing trends, featuring copious amounts of data as well as the end of Moore’s law, puts greater emphasis on extremely scalable algorithms such as those with nearly linear running times. This project addresses these modern challenges by developing faster algorithms for a selection of fundamental problems in combinatorial optimization, building towards a broad algorithmic foundation of scalable algorithms. This project augments theoretical algorithms research with efforts to develop implementations and expand applications, in part through the Computational Science and Engineering group at Purdue among other avenues. This project will support two or more PhD students and the investigator will organize activities to promote research in fast algorithms, with particular effort to recruit and train students from underrepresented minorities. The investigator will integrate modern and advanced algorithmic techniques informed by the research initiatives of this project into the curriculum at Purdue both at the undergraduate and graduate level. This project encompasses a family of interrelated problems that investigate the rich and timely interplay of (a) linear programs and continuous optimization, (b) graph structure and algorithms, (c) randomization, and (d) data structures. They are grouped into the following verticals. The first group, on accelerating positive linear programs, focuses on reducing the running-time dependence on the relative-error parameter for a variety of linear programs useful in combinatorial optimization. The second group of problems, on fast approximations for the traveling salesman problem (TSP), seeks to develop linear-time approximations for variations of TSP as well as related problems of independent interest. The third and final group of problems develops fast approximation algorithms for connectivity, including problems for both undirected and directed graphs. There are rich theoretical connections across these problems that this project leverages and further develops. 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.