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

理论算法领域长期以来一直强调多项式和指数运行时间之间的区别，这为计算作为一门科学形成了良好的理论基础，也对许多技术进步起到了稳健的作用。最近的计算趋势，以大量的数据和摩尔定律的终结为特征，更加强调极端可扩展的算法，比如那些几乎线性运行时间的算法。该项目通过为组合优化中的一些基本问题开发更快的算法来解决这些现代挑战，建立可扩展算法的广泛算法基础。该项目通过努力开发实现和扩展应用来增强理论算法研究，部分通过普渡大学的计算科学与工程小组以及其他途径。该项目将支持两名或两名以上的博士生，研究者将组织活动促进快速算法的研究，特别努力招募和培训来自代表性不足的少数民族的学生。研究者将整合现代和先进的算法技术，通过这个项目的研究计划，在普渡大学的本科和研究生阶段的课程中。该项目包含一系列相互关联的问题，研究(a)线性规划和连续优化，(b)图结构和算法，(c)随机化和(d)数据结构的丰富和及时的相互作用。它们被分为以下垂直方向。第一组，关于加速正线性规划，着重于减少对组合优化中有用的各种线性规划的相对误差参数的运行时间依赖。第二组问题，关于旅行推销员问题（TSP）的快速逼近，寻求发展TSP变化的线性时间逼近以及相关的独立兴趣问题。第三组也是最后一组问题开发了连接的快速近似算法，包括无向图和有向图的问题。这些问题之间有丰富的理论联系，本项目利用和进一步发展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.