Approximation Algorithms for NP-Hard Problems

点击翻译按钮获取中文摘要

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).