A Primal-Dual Clustering Technique with Applications in Network Design

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 F OREST 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 T REE [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 P RIZE-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 S TEINER 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.