2(1 – 1/ℓ)-Factor Steiner Tree Approximation in Õ(n^1/3) Rounds in the CONGESTED CLIQUE
Parikshit Saikia, Sushanta Karmakar · 2019
We study the Steiner tree problem in the CONGESTED CLIQUE model of distributed computing. We present a deterministic distributed approximation algorithm that computes a Steiner tree in Õ(n1/3) rounds and Õ(n7/3) messages for a given undirected weighted graph of n nodes with the approximation factor 2(1 - 1/ℓ) of the optimal, where ℓ is the number of terminal leaf nodes in the optimal Steiner tree. Note here that the Õ(·) notation hides polylogarithmic factors in n. To the best of our knowledge, this is the first work to study the Steiner tree problem in the CONGESTED CLIQUE model.