CAREER: New Mathematical Programming Techniques in Approximation and Online Algorithms

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

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.