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

AF：SMALL：匹配网络设计完整性差距的近似算法

• 批准号: 1527032
• 负责人: Ramamoorthi Ravi
• 金额: $ 40万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1527032&HistoricalAwards=false
• 关键词: AF; SMALL; Approximation; Algorithms; Matching

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.

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