Approximate Algorithms for Stochastic Network Design

Abstract

I study the problems of optimizing a range of stochastic processes occurring in networks, such as the information spreading process in a social network, species migration processes in landscape network, virus spreading process in human contact network. The standard network design frameworks, such as Steiner tree problem and survival network design problem, fail to capture certain properties of these problems. To solve the problems, the existing techniques, such as standard mixed integer program solver, greedy algorithms or heuristic based methods, also suffer from limited scalability or poor performance. My thesis contributes to both modeling and algorithm development. My first goal is to define a unifying network design framework called stochastic network design (SND) to model a broad class of network design problems under stochasticity. My second goal, which is my major focus, is to design effective and scalable general-purpose approximate algorithms to solve problems that can be formulated by the SND framework.