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-Median，定向的Steiner Tree，Beck-Fiala猜想，无可限制的流量和在线多商品的中心问题。该项目还将扩展所得技术的适用性，以诸如组合和运营研究等领域。