Dehghani, Sina ;
Ehsani, Soheil ;
Hajiaghayi, MohammadTaghi ;
Liaghat, Vahid ;
Seddighin, Saeed
Greedy Algorithms for Online Survivable Network Design
Abstract
In an instance of the network design problem, we are given a graph G=(V,E), an edgecost function c:E > R^{>= 0}, and a connectivity criterion. The goal is to find a minimumcost subgraph H of G that meets the connectivity requirements. An important family of this class is the survivable network design problem (SNDP): given nonnegative integers r_{u v} for each pair u,v in V, the solution subgraph H should contain r_{u v} edgedisjoint paths for each pair u and v.
While this problem is known to admit good approximation algorithms in the offline case, the problem is much harder in the online setting. Gupta, Krishnaswamy, and Ravi [Gupta et al., 2012] (STOC'09) are the first to consider the online survivable network design problem. They demonstrate an algorithm with competitive ratio of O(k log^3 n), where k=max_{u,v} r_{u v}. Note that the competitive ratio of the algorithm by Gupta et al. grows linearly in k. Since then, an important open problem in the online community [Naor et al., 2011; Gupta et al., 2012] is whether the linear dependence on k can be reduced to a logarithmic dependency.
Consider an online greedy algorithm that connects every demand by adding a minimum cost set of edges to H. Surprisingly, we show that this greedy algorithm significantly improves the competitive ratio when a congestion of 2 is allowed on the edges or when the model is stochastic. While our algorithm is fairly simple, our analysis requires a deep understanding of kconnected graphs. In particular, we prove that the greedy algorithm is O(log^2 n log k)competitive if one satisfies every demand between u and v by r_{uv}/2 edgedisjoint paths. The spirit of our result is similar to the work of Chuzhoy and Li [Chuzhoy and Li, 2012] (FOCS'12), in which the authors give a polylogarithmic approximation algorithm for edgedisjoint paths with congestion 2.
Moreover, we study the greedy algorithm in the online stochastic setting. We consider the i.i.d. model, where each online demand is drawn from a single probability distribution, the unknown i.i.d. model, where every demand is drawn from a single but unknown probability distribution, and the prophet model in which online demands are drawn from (possibly) different probability distributions. Through a different analysis, we prove that a similar greedy algorithm is constant competitive for the i.i.d. and the prophet models. Also, the greedy algorithm is O(log n)competitive for the unknown i.i.d. model, which is almost tight due to the lower bound of [Garg et al., 2008] for single connectivity.
BibTeX  Entry
@InProceedings{dehghani_et_al:LIPIcs:2018:9156,
author = {Sina Dehghani and Soheil Ehsani and MohammadTaghi Hajiaghayi and Vahid Liaghat and Saeed Seddighin},
title = {{Greedy Algorithms for Online Survivable Network Design}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {152:1152:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9156},
URN = {urn:nbn:de:0030drops91569},
doi = {10.4230/LIPIcs.ICALP.2018.152},
annote = {Keywords: survivable network design, online, greedy}
}
04.07.2018
Keywords: 

survivable network design, online, greedy 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 