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) P
RIZE-COLLECTING
S
TEINER
T
REE
, P
RIZE-COLLECTING
TSP, and P
RIZE-COLLECTING
S
TROLL
. 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 S
TEINER
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 S
TEINER
F
OREST
on planar graphs. Prize-collecting clustering paradigm allows us to generalize PTASes for Euclidean S
TEINER
T
REE
[Aro98, Mit99], Euclidean S
TEINER
F
OREST
[BKM08], and planar S
TEINER
T
REE
[BKM09]. Our algorithm builds upon the
brick decomposition technique of Borradaile et al. [BKM09], in addition to a nontrivial PTAS for bounded-treewidth S
TEINER
F
OREST
.
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 P
RIZE-COLLECTING
S
TEINER
T
REE
(P
RIZE-COLLECTING
TSP, and P
RIZE-COLLECTING
S
TROLL
) as well as M
ULTIPLICATIVE
P
RIZE-COLLECTING
S
TEINER
F
OREST
, 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 P
RIZE-COLLECTING
S
TEINER
F
OREST
.
We hope that the prize-collecting clustering paradigm can be used to give PTASes and improved approximation guarantees for several other network design problems.
