@inproceedings{jin2024streaming,
author = {Jin, Ce and Kapralov, Michael and Mahabadi, Sepideh and Vakilian, Ali},
title = {Streaming Algorithms for Connectivity Augmentation},
booktitle = {International Colloquium on Automata, Languages, and Programming (ICALP)},
year = {2024},
month = {July},
abstract = {We study the -connectivity augmentation problem (-CAP) in the single-pass streaming model. Given a -edge connected graph  that is stored in memory, and a stream of weighted edges  with weights in , the goal is to choose a minimum weight subset  such that  is -edge connected. We give a -approximation algorithm for this problem which requires to store  words. Moreover, we show our result is tight: Any algorithm with better than -approximation for the problem requires  bits of space even when . This establishes a gap between the optimal approximation factor one can obtain in the streaming vs the offline setting for -CAP. We further consider a natural generalization to the fully streaming model where both  and  arrive in the stream in an arbitrary order. We show that this problem has a space lower bound that matches the best possible size of a spanner of the same approximation ratio. Following this, we give improved results for spanners on weighted graphs: We show a streaming algorithm that finds a -approximate weighted spanner of size at most  for integer , whereas the best prior streaming algorithm for spanner on weighted graphs had size depending on . Using our spanner result, we provide an optimal -approximation for -CAP in the fully streaming model with  words of space. Finally we apply our results to network design problems such as Steiner tree augmentation problem (STAP), -edge connected spanning subgraph (-ECSS), and the general Survivable Network Design problem (SNDP). In particular, we show a single-pass -approximation for SNDP using  words of space, where  is the maximum connectivity requirement},
url = {http://approjects.co.za/?big=en-us/research/publication/streaming-algorithms-for-connectivity-augmentation/},
}