Computer Science Masters Thesis Presentation

Wednesday, December 16, 2015 - 10:00am


McWilliams Classroom 4303 Gates & Hillman Centers



For More Information, Contact:

In this thesis, we present approximation algorithms for variants and special cases of the Stochastic Unsplittable Flow Problem (hereafter, sUFP). The objective of the sUFP is to optimally schedule tasks from a given set of tasks on an underlying graph, each of which is specified by a stochastic demand, a payoff and a pair of vertices between which it must be scheduled.Even very special cases of the sUFP, such as the sUFP on a single-edge graph with deterministic demands, are known to be NP-hard. We present new polytime constant-factor approximation algorithms for the sUFP on Paths and Trees and for extensions where each task may correspond to more than two vertices. We consider two settings - a special-case in which all the capacities are equal and the general-case in which the capacities are arbitrary. In dealing with arbitrary capacities, we assume that the distribution underlying the demand for each task has maximum attainable value less than or equal to the least capacity among the edges in the graph, operating under what is known as the No Bottleneck Assumption. Our approximation algorithms are obtained by combining approximations for instances in which all tasks are small and for those in which all tasks are large. They provide an approximation to a linear programming relaxation and hence may perform significantly better in practice than the guarantees we establish. These algorithms do not make decisions based on results of previously instantiated tasks, and are classified as non-adaptive algorithms, which leads to the result that the adaptivity gaps for these problems are bounded by a constant. Thesis Committee: Anupam Gupta (Chair) R Ravi Danny Sleator


Masters Thesis Presentation