Date of Award
Doctor of Philosophy (PhD)
Dean, Brian C
Goddard , Wayne D
Srimani , Pradip K
Jacobs , David P
This dissertation discusses algorithms and results on several NP–hard graph problems which can all be classified as network interdiction and network fortification problems.
The first problem studied, the multiway cut problem, is a generalization of the well–studied s–t min–cut problem, in which we must remove a minimum–cost subset of edges from a graph so that r > 2 designated terminals become disconnected from each other. We investigate an approximation algorithm for general r with a relatively simple analysis guaranteeing an approximation ratio ≤ 1.4647 − epsilonr, where epsilonr is a small constant related to the number of terminals r. This improves on the 1.5 − 1/r guarantee of Calinescu et al. and is somewhat simpler than the 1.3438 − epsilonr result of Karger et al. We also perform three types of computational experiments to obtain empirical results and offer observations for the r = 4 case, based on small discretized instances.
Next, we introduce a generalization of the multiway cut problem, called the k–hurdle multiway cut problem, in which every terminal–terminal path must be cut not merely once, but k > 1 times. We present a half–integrality proof implying a 2–approximation to the problem, a (1, k−1)–pseudo approximation result, and also a true approximation algorithm with performance guarantee 2(1 − 1/r). This guarantee is unlikely to be improved upon, as we demonstrate an approximation–preserving reduction from the well–known vertex cover problem.
A related problem we also study is the k–hurdle multicut problem, where we have a list of source–sink pairs (i,j), and each source must be separated from its sink kij times. We present a (log(n), ceiling((1−epsilon)kmax))–pseudo approximation algorithm, with approximation guarantee O(log(n)) that guarantees all hurdles will be satisfied if all kij = O(1). We also obtain a 2–approximation for trees, which holds in both the standard k–hurdle multicut problem and a vertex variant, and we consider a hybrid problem of k–hurdle multiway cut and k–hurdle multicut, in which different hurdle counts kij exist between each pair of terminals (i,j), and all form an ultrametric. We demonstrate the half–integrality of this problem, implying a 2–approximation.
Finally, we consider a problem called the network knapsack problem, which is a special case of a packing integer program where the underlying constraint system has a well–defined graph structure. We use dynamic programming to obtain a polynomial time solution on ladders of width k = O(1), and a polynomial time approximation scheme for trees and grids. We also investigate the difficulty of developing approximation algorithms for this problem on low-treewidth graphs and planar graphs.
Whitley, Adam, "Approximation Algorithms for Network Interdiction and Fortification Problems" (2010). All Dissertations. 646.