PhD Proposal: Online Network Design and Prophets: Going Beyond Worst-Case Analysis

Talk
Soheil Ehsani Banafati
Time: 
04.07.2017 12:00 to 13:30
Location: 

AVW 3258

The problem of satisfying connectivity demands in a network while respecting given constraints has been a pillar of the area of network design since decades ago. For instance, in a wireless network one may want to maintain an interconnect between a set of nodes. While this could happen through many different ways, there are objectives such as battery consumption or throughput rate that are preferred to be optimized. Such problems in network design are usually modeled by an underlying graph and a set of requests and the goal is to find an optimum (or near optimum) solution with respect to given constraints.

In this article we study several network design problems in the online setting. First, we introduce the degree-bounded Steiner forest problem and propose a greedy-like algorithm for it. Using the dual-fitting technique we show our algorithm is O(log n)-approximation. Also, we give a hardness example that proves the bound achieved by the algorithm is asymptotically tight. Next, we study the weighted generalization of the problem and design a poly-logarithmic competitive algorithm which exploits the structural properties of Steiner forests and a new LP-solving method. Moreover, we study the online survivable network design problem, in which the goal is to maintain a robust connection between the endpoints of every demand. For this problem we analyze the greedy algorithm by means of Steiner packing and show that it significantly improves the previously existing results if a congestion of 2 is allowed.

In all of the mentioned problems the best approximations are polylogarithmic because of the hard instances that may happen in online scenarios. However, such hard instances are usually unlikely to happen in practice. As a step towards going beyond the worst-case analysis, we study the network design problem under the prophet model, where a statistical data is provided about the future events. We start off with a full treatment of the iid prophet inequality problem which is an important fundamental case. Next, we present a general framework that analyzes the algorithms for the prophet model through an oblivious algorithm for the iid model. We find properties of k-connected graphs and use our framework to prove that the greedy algorithm is constant approximation in the prophet model of the survivable network design problem. Finally, by applying this framework to other problems we achieve constant competitive algorithms for vertex cover, facility location, and set cover in the prophet model.

Examining Committee:

Chair: Dr. Mohammad T. Hajiaghayi

Dept. rep: Dr. Ashok Agrawala

Member: Dr. David Mount