权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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的法定使命，并被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。