CAREER: New Mathematical Programming Techniques in Approximation and Online Algorithms

职业：近似和在线算法中的新数学编程技术

基本信息

批准号：
1750127
负责人：
Viswanath Nagarajan
金额：
$ 50万
依托单位：
Regents of the University of Michigan - Ann Arbor
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-02-01 至 2023-01-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750127&HistoricalAwards=false
关键词：
CAREER New Mathematical Programming Techniques

项目摘要

Numerous applications in engineering, science and business are modeled and solved as combinatorial optimization problems. In today?s digital age, data collection and storage is inexpensive. The bottleneck lies in society's ability to solve increasingly larger problem instances, where the challenge typically stems from computational or informational limitations. This intractability can often be overcome by searching for approximately optimal instead of exactly optimal solutions. This project will design new mathematical-programming-based techniques that are broadly applicable in approximating combinatorial optimization problems. The project will strengthen connections of theoretical computer science to various fields of mathematics such as discrepancy theory, geometry, graph theory, optimization and probability. The PI will also collaborate with industry colleagues to disseminate the theoretical findings on some of the studied problems and assess their practical impact. The educational aspect of this project includes training undergraduate and graduate students, developing new course material and organizing a workshop for high-school teachers. Despite the wide range of possible combinatorial optimization problems, a common approach underlying numerous results in approximation and online algorithms is mathematical programming and rounding. This project will develop new techniques in this area by investigating (1) algorithms based on convex-programming hierarchies, (2) rounding algorithms based on recent advances in algorithmic discrepancy and (3) an online primal-dual framework for convex objectives. This project involves designing general algorithmic techniques (and identifying problem classes to which they apply) as well as improving the state-of-art on central problems such as k-Median, directed Steiner tree, the Beck-Fiala conjecture, unsplittable flow and online multicommodity routing. This project will also expand the applicability of the resulting techniques to areas such as combinatorics and operations research.

工程、科学和商业中的许多应用都是作为组合优化问题进行建模和解决的。在当今的数字时代，数据收集和存储的成本低廉。瓶颈在于社会解决越来越大的问题实例的能力，其中的挑战通常源于计算或信息的限制。这种棘手的问题通常可以通过搜索近似最优解而不是精确最优解来克服。该项目将设计新的基于数学编程的技术，这些技术广泛适用于近似组合优化问题。该项目将加强理论计算机科学与数学各个领域的联系，如差异理论、几何、图论、优化和概率。 PI 还将与业界同行合作，传播有关一些研究问题的理论结果并评估其实际影响。该项目的教育方面包括培训本科生和研究生、开发新课程材料以及为高中教师组织研讨会。尽管可能存在各种各样的组合优化问题，但近似和在线算法中众多结果的常用方法是数学编程和舍入。该项目将通过研究（1）基于凸规划层次结构的算法、（2）基于算法差异最新进展的舍入算法和（3）凸目标的在线原对偶框架来开发该领域的新技术。该项目涉及设计通用算法技术（并识别它们适用的问题类别）以及改进核心问题的最新技术，例如 k 中值、有向 Steiner 树、Beck-Fiala 猜想、不可分割流和在线多商品路由。该项目还将把所得技术的适用性扩展到组合学和运筹学等领域。