Approximation algorithms for NP-hard problems

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

Network design, network flows, and graph connectivity occur as core topics in Theoretical Computer Science, Operations Research, and Combinatorial Optimization. Many important algorithmic 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 and congestion control for urban road traffic. 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. My current and planned research focuses on the following three broad interlocking themes. I discuss two of these topics below, and my proposal discusses all the topics in full. 1. Design of approximately minimum-cost networks, including the Traveling Salesman Problem (TSP) and its variants. 2. Design of networks subject to node-connectivity requirements. 3. Lift-and-Project methods for the Asymmetric TSP and related problems. The most famous problem in all of discrete optimization is the TSP. The best known algorithmic result is the 3/2-approximation algorithm due to Christofides from 1976. It has long been conjectured that there exists a 4/3-approximation algorithm for the TSP, and that there exists a 3/2-approximation algorithm for a variant called the s-t path TSP. Two of the outstanding open questions on this topic that I am researching are the following: (*) Improve on the approximation guarantee of 7/5 for an important special case called the GRAPHIC TSP, possibly based on a combination of LP-rounding techniques and ear-decomposition techniques. (*) Improve on the approximation guarantee of 8/5 for the s-t path TSP, possibly based on LP-rounding techniques, coupled with improved structural results on the support graph of LP solutions. The second broad theme of my research addresses the design of networks subject to node-connectivity requirements. One of the basic problems in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some pre-specified connectivity requirements. The area of minimum-cost network design subject to EDGE-connectivity requirements flourished in the 1990s, and there were a number of landmark results. Progress has been much slower on similar problems with NODE-connectivity requirements, despite more than a decade of active research. Very recently, in a paper co-authored with L.Vegh (Proc. IEEE FOCS 2013), I have obtained a major advance on a fundamental problem in this area: we have a 6-approximation algorithm for the minimum-cost k-node connected spanning subgraph problem, assuming that the number of nodes is at least k^4. Our results and techniques have opened up many new directions in the design of networks subject to node-connectivity requirements. I plan to continue research on these topics, together with graduate students and postdocs. In summary, the high-level goal of my research agenda is to provide significant advances in the areas of Network Design and related areas of Combinatorial Optimization. This has the potential to improve the results and techniques available to all researchers who work in this core area of the computational sciences. Problems such as the TSP are ubiquitous in all modern societies, including Canada; the economy and infrastructure are based on logistics, transport, networks, and on the optimal allocation of scarce resources to critical tasks.