Approximation Algorithms for NP-Hard Problems

网络设计、网络流量和图形连通性是理论计算机科学、运筹学和组合优化的核心主题。在这些主题的背景下，发展了重要的算法和结构范例，例如最小生成树的贪婪算法和网络流的最大流最小割定理。此外，这些主题还出现在许多实际环境中，例如容错通信网络的设计、道路交通的拥塞控制和社会网络的分析。在实际环境中出现的许多问题都是NP难的。这意味着不能在合理的运行时间内计算最优解，模为P.no.=NP猜想。因此，研究集中在近似算法上，即找到在最优解的保证因子内的解的高效算法。 在近似算法的设计和分析中，我使用了以下方法：组合优化(特别是匹配和网络流)、线性规划松弛舍入、原始对偶方法、提升和投影方法以及动态规划的算法和理论。 我计划在我最近的主要进展和期刊出版物的基础上，与我的研究生和合著者一起解决网络设计中的一些未决问题。 我的研究计划的三个关键模块总结如下。 (A)针对节点的网络设计--连接要求 网络设计中的一个基本问题，称为NC-SNDP，是寻找给定网络G的一个最小费用子网络H，使得H满足某些预先指定的节点连通性要求。我(和我的研究生们)正在研究一个基本的公开问题：设计一个NC-SNDP的近似算法，它的保证与网络G的节点/边/终端的数量无关。 (B)稀树和旅行商问题(TSP) 生成树T的细度参数是所有割中T的边的比例在割中的最大值。Goddyn猜想，对于任何所需的稀疏度，具有足够大的边连通性的图都有一个具有该稀疏度的生成树。一个算法(多时间)证明将使ATSP的近似算法取得重大进展。我的长期目标就是这样的证明。我正在(和我的研究生们)设计高效的算法，在特殊的图类中寻找稀疏的生成树。 (C)用于组合优化的升降机和项目系统 该领域的一个关键问题是改进最小代价2-边连通生成子图(2-ECSS)问题的二的逼近保证。我的直接目标是对于这个问题的一个特殊情况，即森林增强问题(FAP)，得到一个比两个更好的近似保证，相对于通过Lift-and-Project方法获得的FAP的松弛。这将推广我与高(我已完成的博士生)发表的结果。

Network design, network flows, and graph connectivity are core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Important algorithmic and structural paradigms were developed in the context of these topics, such as the greedy algorithm for minimum spanning trees and the max-flow min-cut theorem for network flows. Moreover, these topics arise in many practical contexts such as the design of fault-tolerant communication networks, congestion control for road traffic, and the analysis of social networks. Many of the problems arising in practical contexts are NP-hard. This means that optimal solutions cannot be computed in a reasonable running time, modulo the P .not.= NP conjecture. Hence, research has focused on approximation algorithms, i.e., efficient algorithms that find solutions that are within a guaranteed factor of the optimal solution. In the design and analysis of approximation algorithms, I am using methods such as: algorithms and theory from combinatorial optimization (in particular, matchings and network flows), rounding of linear-programming relaxations, the primal-dual method, lift-and-project methods, and dynamic programming. I plan to attack some outstanding open questions in network design jointly with my graduate students and co-authors, building on my recent major advances and journal publications. Three key modules of my research program are summarized below. (A) Network Design for Node-Connectivity Requirements A basic problem in network design, called the NC-SNDP, is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified NODE-connectivity requirements. I am attacking (with my grad students) a fundamental open problem: design an approximation algorithm for NC-SNDP whose guarantee is independent of the number of nodes/edges/terminals of the network G. (B) Thin trees and the Traveling Salesman Problem (TSP) The thinness parameter of a spanning tree T is the maximum over all cuts of the proportion of the edges of T in the cut. Goddyn conjectured that for any required thinness, a graph of sufficiently large edge-connectivity has a spanning tree with that thinness. An algorithmic (poly-time) proof would give major advances on approximation algorithms for ATSP. My long-term goal is such a proof. I am designing (with my grad students) efficient algorithms for finding thin spanning trees in special classes of graphs. (C) Lift-and-Project Systems for Combinatorial Optimization A key open question in the area is to improve on the approximation guarantee of two for the minimum-cost 2-edge connected spanning subgraph (2-ECSS) problem. My immediate goal is to derive an approximation guarantee better than two for a special case of this problem called the Forest Augmentation Problem (FAP) relative to a relaxation of FAP obtained via Lift-and-Project methods. This will generalize results that I have published with Gao (my completed Ph.D. student).