CAREER: New Mathematical Programming Techniques in Approximation and Online Algorithms

在工程、科学和商业中的许多应用都被建模和求解为组合优化问题。在今天？S数字化时代，数据采集和存储都很便宜。瓶颈在于社会解决越来越大的问题的能力，这些问题的挑战通常源于计算或信息限制。这一难题通常可以通过寻找近似最优解而不是精确最优解来克服。这个项目将设计新的基于数学规划的技术，这些技术广泛适用于近似组合优化问题。该项目将加强理论计算机科学与数学各个领域的联系，如差异论、几何学、图论、最优化和概率论。该委员会亦会与业界同僚合作，传播有关部分研究问题的理论研究结果，并评估其实际影响。该项目的教育方面包括培训本科生和研究生，开发新的课程材料，并为高中教师组织讲习班。尽管可能的组合优化问题范围很广，但在近似和在线算法中的众多结果背后的一个常见方法是数学规划和舍入。这个项目将通过研究(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.