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.