Approximation Algorithms for Network Interdiction and Fortification Problems

Author

Adam Whitley, Clemson UniversityFollow

Date of Award

12-2010

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Legacy Department

Computer Science

Committee Chair/Advisor

Dean, Brian C

Committee Member

Goddard , Wayne D

Committee Member

Srimani , Pradip K

Committee Member

Jacobs , David P

Abstract

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 − epsilon_r, where epsilon_r 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 − epsilon_r 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 k_ij times. We present a (log(n), ceiling((1−epsilon)k_max))–pseudo approximation algorithm, with approximation guarantee O(log(n)) that guarantees all hurdles will be satisfied if all k_ij = 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 k_ij 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.

Recommended Citation

Whitley, Adam, "Approximation Algorithms for Network Interdiction and Fortification Problems" (2010). All Dissertations. 646.
https://open.clemson.edu/all_dissertations/646