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

AF：小：更快更好的算法，并通过数学编程松弛

基本信息

批准号：
1910149
负责人：
Chandra Chekuri
金额：
$ 30万
依托单位：
University of Illinois at Urbana-Champaign
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2019
资助国家：
美国
起止时间：
2019-10-01 至 2024-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910149&HistoricalAwards=false
关键词：
AF Small Faster Better Algorithms

项目摘要

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.

优化算法支撑着计算机科学、工程和社会科学的基本进步。例如，机器学习近年来取得的巨大成功部分归功于一类连续优化算法的重要作用。在另一个方向上，基于连续优化和离散优化之间富有成效的相互作用，在图和网络的基本和广泛应用的问题上取得了许多突破性进展，例如最大流和最小割问题。不断增加的数据集规模和新的计算模型需要优化算法的进一步进步，才能获得数据革命的回报。该提案旨在为一类连续优化问题开发更快的近似算法，并利用这些算法为离散和组合优化中几个经过充分研究和应用的问题获得更快的近似算法。该项目将支持和培训伊利诺伊大学厄巴纳-香槟分校的一名博士生进行算法设计和分析。研究人员计划就正线性规划快速逼近方案的最新进展撰写一份调查报告，重点关注组合优化中出现的隐式规划的应用。研究人员将继续在伊利诺伊大学开发和教授大数据算法课程，讲义和相关材料将公开。该项目的技术重点是通过数学编程松弛来开发快速逼近算法离散优化中的一些基本问题。这涉及开发用于解决松弛问题的快速算法以及用于舍入的快速算法。离散方法和连续方法之间的相互作用将是一个重要的技术观点。该项目将有两个重点。首先是开发用于求解正线性规划的快速算法和一些具体应用。特别关注组合优化中出现的隐式线性程序。第二个重点是针对旅行推销员问题（TSP）以及无向和有向图中的相关问题的快速算法。还将考虑子模块目标函数的应用。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。