PhD Defense: Dissertation Defense for Soheil Ehsani
Networks play a key role in today's modern world. From connecting friends in social networks to distributing electricity from producers to consumers in a power grid, one can observe the wide range of applications networks have in our lives. The rise of wireless communication technology has even added to the complexity of networks in the recent decades. In this dissertation, we study networks from a theoretical perspective and try to give efficient algorithms for fundamental network design problems in the online setting, in which the demands have to be satisfied in a real-time fashion. Furthermore, motivated by the advances in statistical and machine learning tools and inspired by the prophet inequality problem, we introduce the prophet setting in which the algorithm has incomplete information about future demands. By presenting a general framework, we demonstrate how this setting can lead to improving algorithms for some of the classical network design problems in real-life applications.
This dissertation begins with a study of variants of the Steiner tree problem, which is a common mathematical model for finding optimum connected structures for a set of users in a network (generalizes spanning trees). First, we introduce the online degree-bounded Steiner forest problem that considers an extra constraint of bounding the congestion on nodes of the graph while satisfying demands in a real-time fashion. For this problem, we design a simple but tight greedy algorithm in which the maximum congestion is an O(log n)-approximation of the optimum. Besides, we design a novel tool for solving online mixed packing/covering linear programs to attack the edge-weighted generalization of the problem. To this end, we use structural properties of Steiner forests and rewrite the problem using a modified integer program and then apply our tool to it, which results in bicriteria (for degree and weight) poly-logarithmic approximation algorithms.
Unlike their online variants, network design problems in the online setting often have super-constant hardnesses. This issue is due to the assumption of complete uncertainty about the future demands in the traditional online setting. However, in real life problems, the input demands sometimes come from distributions that are specific to the application and conditions of the problem. To model this feature for network design problems, we introduce the prophet setting in which the input consists of the initial conguration of the network as well as the probability distribution for each demand. Next, we study the prophet inequality problem in the special case of i.i.d. and general cases of matroids (generalizes spanning tree) and combinatorial auctions (generalizes bipartite matchings). Finally, we conclude this dissertation by revisiting online network design problems in the prophet setting and proposing improving approximation algorithms for them.
Chair: Dr. Mohammad Hajiaghayi
Dean’s rep: Dr. Peter Cramton
Members: Dr. William Gasarch
Dr. Aravind Srinivasan
Dr. David Mount