@inproceedings{chekuri2025streaming,
author = {Chekuri, Chandra and Jain, Rhea and Mahabadi, Sepideh and Vakilian, Ali},
title = {Streaming Algorithms for Network Design},
booktitle = {International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX)},
year = {2025},
month = {August},
abstract = {We consider the Survivable Network Design problem (SNDP) in the single-pass insertion-only streaming model. The input to SNDP is an edge-weighted graph G=(V,E) and an integer connectivity requirement  r(u,v) for each u,v∈V. The objective is to find a min-weight subgraph H⊆G s.t., for every pair of u,v∈V,u  and v are r(uv)-edge/vertex-connected. Recent work by Jin et al. [JKMV24] obtained approximation algorithms for edge-connectivity augmentation, and via that, also derived algorithms for edge-connectivity SNDP (EC-SNDP). We consider vertex-connectivity setting (VC-SNDP) and obtain several results for it as well as improved results for EC-SNDP.

 	We provide a general framework for solving connectivity problems in streaming; this is based on a connection to fault-tolerant spanners. For VC-SNDP, we provide an O(tk)-approximation in Õ(k^[1-1/t] n^[1+1/t]) space, where k is the maximum connectivity requirement, assuming an exact algorithm at the end of the stream. Using a refined LP-based analysis, we provide an O(βt)-approximation where β is the integrality gap of the natural cut-based LP relaxation. When applied to the EC-SNDP, our framework provides an O(t)-approximation in Õ(k^[1/2 - 1/(2t)] n^[1+1/t]+kn) space, improving the O(t log k)-approximation of [JKMV24] using Õ(k n^[1+1/t]) space; this also extends to element-connectivity SNDP.
 	We consider vertex connectivity-augmentation in the link-arrival model. The input is a k-vertex-connected subgraph G, and the weighted links L arrive in the stream; the goal is to store the min-weight set of links s.t. G∪L is (k+1)-vertex-connected. We obtain O(1) approximations in near-linear space for k=1,2. Our result for k=2 is based on SPQR tree, a novel application for this well-known representation of 2-connected graphs.},
url = {http://approjects.co.za/?big=en-us/research/publication/streaming-algorithms-for-network-design/},
}