A Primal-Dual Clustering Technique with Applications in Network Design (thesis)
Abstract:
Network design problems deal with settings where the goal is to design a network (i.e., find a subgraph of a given graph) that satisfies certain connectivity requirements. Each requirement is in the form of connecting (or, more generally, providing large connectivity between) a pair of vertices of the graph. The goal is to find a network of minimum length, and in some cases requirements can be compromised after paying their "penalties." These are usually called prize-collecting Steiner network problems.
In practical scenarios of physical networking, with cable or fiber embedded in the ground, crossings are rare or nonexistent. Hence, planar instances of network design problems are a natural subclass of interest. We can usually take advantage of this structure to find better performance guarantees.
In this thesis, we develop a primal-dual clustering technique called "prize-collecting clustering," which is used to give improved approximation algorithms for several planar and nonplanar network design problems. The technique is based on a famous moat growing procedure due to Agrawal, Klein, Ravi [AKR95] and Goemans and Williamson [GW95]. It provides a paradigm for clustering the vertices of a graph according to their "budgets" such that vertices of the same cluster are close compared to their budgets, whereas distinct clusters are far compared to their budgets.
We first improve the approximation ratio of (nonplanar) Prize-collecting Steiner Tree, Prize-collecting TSP, and Prize-collecting Stroll. For 17 years, the best known results for these problems were 2-approximation algorithms of Goeman and Williamson [AKR95]. We show how to get around the integrality gap of the natural linear-programming relaxation, and achieve an approximation ratio of 2 − c (for a fixed, yet small c).
Next we give a thorough complexity study of Steiner Forest for graphs of treewidth two, three, and O(1) as well as planar and bounded-genus graphs. In particular, we provide a polynomial-time approximation scheme (PTAS) for Steiner Forest on planar graphs. Prize-collecting clustering paradigm allows us to generalize PTASes for Euclidean Steiner Tree [Aro98, Mit99], Euclidean Steiner Forest [BKM08], and planar Steiner Tree [BKM09]. Our algorithm builds upon the brick decomposition technique of Borradaile et al. [BKM09], in addition to a nontrivial PTAS for bounded-treewidth Steiner Forest.
Finally, we look at several prize-collecting Steiner network problems on planar (and bounded-genus) graphs. We present a reduction from these instances to the bounded-treewidth special cases of those problems implying, in particular, that a PTAS carries over. For Prize-collecting Steiner Tree (Prize-collecting TSP, and Prize-collecting Stroll) as well as Multiplicative Prize-collecting Steiner Forest, we show that this leads to PTASes. However, we show that several seemingly simple problems in this area are APX-hard. As a result, we give the first provable separation between the complexity of a natural network design problem and its prize-collecting variant: a PTAS for planar Steiner Forest and APX-hardness for planar Prize-collecting Steiner Forest.
We hope that the prize-collecting clustering paradigm can be used to give PTASes and improved approximation guarantees for several other network design problems.
