Polyhedral and Algorithmic Methods in Network Connectivity

 This dissertation contains five chapters, each addressing an algorithmic or polyhedral problem in network connectivity and combinatorial optimization. 

The first three chapters consider problems, both classical and novel, in the field of network con?nectivity augmentation. In these problems, we seek to augment a given graph by making it more resilient to edge failures. The latter two chapters address problems related to Set Cover polyhedra. 

In the first and second chapters, we consider connectivity augmentation in the “Steiner” setting. In this setting, we are only interested in the connectivity between a specified set of terminal nodes, rather than the global connectivity of the network. In chapter one, we define the Steiner Tree Augmentation Problem, the natural generalization of the Tree Augmentation Problem to the Steiner setting. We employ a relative greedy algorithm to give a 1 + ln(2) + ε approximation, the first algorithm for this problem with approximation ratio below 2. We then show how to use the local search methodology of Traub and Zenklusen to bring down the approximation ratio to 1.5 + ε. 

In chapter two, we define the more general Steiner Connectivity Augmentation Problem (k-SCAP): given a Steiner k-edge-connected graph, augment it so that the Steiner edge-connectivity increases to k + 1. We also define the k-Steiner Augmentation of a Graph problem (k-SAG), which is a special case of k-SCAP but still generalizes the global connectivity augmentation problem. We employ a relative greedy technique to give a 1 + ln(2) + ε approximation for k-SCAP when k = 2, and a 1.5 + ε approximation for k-SAG for any k. 

In the third chapter, we consider the well-known Tree Augmentation Problem (TAP) where the goal is to increase the edge-connectivity of a tree by 1. We take a polyhedral perspective, and show that the integrality gap of a linear relaxation for TAP (known as the ODD-LP) has integrality gap upper bounded by (2 − 1 2 k−1 ) for depth-k trees. For constant-depth trees, this is the first known linear relaxation for TAP with gap less than 2 which can still be optimized over in polynomial time. The proofs also yield approximation algorithms with matching guarantees. 

In chapter four, we define a matroidal generalization of the Tree Augmentation Problem, called the Base Augmentation Problem. In the Base Augmentation Problem, the goal is to add elements to a given base of a matroid so that we obtain a set which remains full rank after any of its elements are deleted. The Tree Augmentation Problem arises when the matroid is graphic. We characterize the approximability of the Base Augmentation Problem for several common classes of matroids, showing that it is Set-Cover hard for Transversal and Binary matroids, but polynomial time solvable for Laminar Matroids. We finish this chapter with a Conjecture on the complexity of the Base Augmentation Problem for regular matroids. In the final chapter, we consider a problem related to packing and covering in directed graphs. Woodall conjectured in 1976 that in any digraph, the minimum cardinality of a directed cut is equal to the maximum number of pairwise arc-disjoint directed joins. In this chapter, we describe progress towards resolving this question. In particular, we reduce the problem to a class of bipartite, “semi-regular” instances and use this to show the existence of an admissible dijoin, as well as various special cases of Woodall’s conjecture depending on the “balancedness” of the digraph