AF: SMALL: Approximation Algorithms Matching Integrality Gaps for Network Design

实践中经常出现的优化问题可以归结为设计连接特定地点的适当网络的问题。许多这样的网络设计问题，如旅行商问题，在计算上很难准确解决；然而，已经设计出了快速运行但提供接近最优解的近似算法来解决这些问题，通常使用这些问题作为样本来开发新的技术。这些用于设计近似算法的大量技术基于应用线性规划的数学建模形式主义来获得起点，并使用不同的方法将它们转换为廉价的实际解。本项目将研究线性规划形式下的一些典型网络设计问题，以确定其精度的界限。在这个过程中，该项目将尝试发现设计这种近似算法的新技术，增加现有的工具包。该项目的方法将有助于为许多网络设计问题设计新的独立解决方案，以及增强使用线性规划框架的现有方法。该项目将综合算法设计、最优化理论和组合离散数学的不同想法，并将通过支持两名女性博士生来扩大参与范围。该教育计划将把结果传播给计算机科学、数学、运筹学和商业领域的广大受众，这些领域的PI是一名教授。本课题研究的问题集包含了近似算法理论中的一些长期未解决的问题，例如对称旅行商问题及其变种：旅行商路径问题和两边连通子图问题；它还包括在各种网络设计应用中出现的其他经典问题，例如树的增加和获奖的Steiner森林。所有这些问题都有一个共同的性质，即对于它们的自然线性规划松弛，这些松弛的极限，也就是它们的积分间隙，还没有确定。该项目的目标是设计新的近似算法，具有与这些问题的确切完整性差距相匹配的性能比。这些算法将基于先进的现有技术，如原始对偶方法和迭代舍入，并开发基于结构分解的新方法。

Optimization problems that often arise in practice can be cast as those of designing appropriate networks that connect specified locations. Many such network design problems such as the traveling salesperson problem are computationally hard to solve exactly; nevertheless, approximation algorithms that run quickly yet deliver near-optimal solutions have been devised for solving them, often using these problems as exemplars to develop new techniques. A large set of these techniques for designing approximation algorithms are based on applying the mathematical modeling formalism of linear programming to obtain a starting point, and using different ways to convert them to actual solutions that are cheap. This project will study some prototypical network design problems under the linear programming formalism to establish the limits of its accuracy. In the process, the project will attempt to discover new techniques for designing such approximation algorithms, adding to the existing toolkit. Methods from the project will be useful in designing new stand-alone solutions for many network design problems as well as enhancing current methods that employ the linear programming framework. The project will synthesize diverse ideas from algorithm design, optimization theory and combinatorial discrete mathematics, and will broaden participation by supporting two female doctoral students. The educational plan will disseminate the results to a broad audience in Computer Science, Mathematics, Operations Research and Business where the PI is a professor. The set of problems examined in this project contains some of the long standing open problems in the theory of approximation algorithms, such as the symmetric traveling salesperson problem and its variants: the traveling salesperson path and two-edge-connected subgraph problems; it also includes other classical problems such as tree augmentation and prize-collecting Steiner forest that arise in a variety of network design applications. All these problems share the property that for their natural linear programming relaxations, the limits of these relaxations, also known as their integrality gaps, have not yet been established. The goal of the project is to design new approximation algorithms with performance ratios that match the exact integrality gap for these problems. These algorithms will be based on advancing current techniques such as primal-dual methods and iterated rounding, and developing new methods based on structural decompositions.