AF: Small: Approximation Algorithms for Network Design

网络设计中的基本问题已成为开发新技术和评估其组合优化有效性的基准。本提案将研究一类连通性问题，包括旅行销售人员问题及其密切相关的变体，如桥梁连通性增强问题，两边连通子图问题和顶点连通性网络设计问题，以便通过推进现有技术和开发新方法来设计改进的近似算法。该建议还从实践中为网络设计问题开发了新的理论模型，这些模型在信息聚合中包含了子附加需求，并在物流规划中集成了库存存储和车辆路线成本。由于其应用的普遍性和理论的基础性，网络设计问题在实践和理论上都具有重要意义。开发的新方法可以纳入实际的启发式方法，用于解决从通信到物流网络的大量应用中出现的现实规模的原型难优化问题。所开发的理论分析将提高这类重要的计算优化问题的快速启发式解的数学可证明性。

Fundamental problems in network design have served as benchmarks for the development of new techniques and evaluating their effectiveness in combinatorial optimization. This proposal will investigate a class of connectivity problems including the traveling salesperson problem and its closely related variants such as the bridge connectivity augmentation problem, two-edge-connected subgraph problem and vertex connectivity network design problems, in order to design improved approximation algorithms by advancing current techniques and developing new methods. The proposal also develops new theoretical models for network design problems from practice that incorporate sub-additive demands in information aggregation, and that integrate inventory storage and vehicle routing costs in logistics planning. Due to the ubiquity of their applications, and the fundamental nature of their theory, network design problems are important both in practice and theory. New methods developed can be incorporated into practical heuristic approaches for solving prototypically hard optimization problems of real-life scale that arise in a host of applications from communications to logistics networks. The theoretical analysis developed will improve the mathematically provable quality of fast heuristic solutions for this important class of computational optimization problems.