Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE

DOI10.1142/S0129054120500367zbMATH Open1458.68278arXiv1907.12011OpenAlexW2966268726MaRDI QIDQ5859656FDOQ5859656

Authors: Parikshit Saikia, Sushanta Karmakar 

Publication date: 19 April 2021

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: The emph{Steiner tree} problem is one of the fundamental and classical problems in combinatorial optimization. In this paper, we study this problem in the $mathcalCONGESTED$ $mathcalCLIQUE$ model of distributed computing and present two deterministic distributed approximation algorithms for the same. The first algorithm computes a Steiner tree in $ildeO(n^{1/3})$ rounds and $ildeO(n^{7/3})$ messages for a given connected undirected weighted graph of $n$ nodes. Note here that $ildeO(cdot)$ notation hides polylogarithmic factors in $n$. The second one computes a Steiner tree in $O(S+loglogn)$ rounds and $O(S(n-t{)}^2+n^2)$ messages, where $S$ and $t$ are the emph{shortest path diameter} and the number of emph{terminal} nodes respectively in the given input graph. Both the algorithms admit an approximation factor of $2(1-1/ell)$, where $ell$ is the number of terminal leaf nodes in the optimal Steiner tree. For graphs with $S=omega(n^{1/3}logn)$, the first algorithm exhibits better performance than the second one in terms of the round complexity. On the other hand, for graphs with $S=ildeo(n^{1/3})$, the second algorithm outperforms the first one in terms of the round complexity. In fact when $S=O(loglogn)$ then the second algorithm admits a round complexity of $O(loglogn)$ and message complexity of $ildeO(n^2)$. To the best of our knowledge, this is the first work to study the Steiner tree problem in the $mathcalCONGESTED$ $mathcalCLIQUE$ model.

Full work available at URL: https://arxiv.org/abs/1907.12011

Recommendations

• Improved distributed steiner forest construction
• Computing and Combinatorics
• The Steiner problem in distributed computing systems
• MST in log-star rounds of congested clique
• MST in \(O(1)\) rounds of congested clique

zbMATH Keywords

Steiner treedistributed approximation algorithmCONGESTED CLIQUEshortest path forest

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Approximation algorithms (68W25) Distributed algorithms (68W15)

Cites Work

• Reducibility among combinatorial problems
• Efficient determination of the transitive closure of a directed graph
• Distributed Computing: A Locality-Sensitive Approach
• Distributed approximation algorithms for weighted shortest paths
• The Steiner tree problem on graphs: inapproximability results
• The round complexity of distributed sorting, extended abstract
• Locality in Distributed Graph Algorithms
• Optimal deterministic routing and sorting on the congested clique
• An improved LP-based approximation for Steiner tree
• The Steiner problem in distributed computing systems
• A fast algorithm for Steiner trees
• A faster approximation algorithm for the Steiner problem in graphs
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• The communication complexity of distributed task allocation
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• A fast distributed approximation algorithm for minimum spanning trees
• Fast partial distance estimation and applications
• A distributed O(1)-approximation algorithm for the uniform facility location problem
• Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds
• On the power of the congested clique model
• Super-fast distributed algorithms for metric facility location
• Distributed computation of large-scale graph problems
• Algebraic methods in the congested clique
• Toward optimal bounds in the congested clique, graph connectivity and MST
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)
• Approximation of distances and shortest paths in the broadcast congest clique
• Lessons from the congested clique applied to MapReduce
• Computing and Combinatorics
• Connectivity Lower Bounds in Broadcast Congested Clique
• Proof-labeling schemes: broadcast, unicast and in between
• Fast Approximate Shortest Paths in the Congested Clique
• MST in \(O(1)\) rounds of congested clique
• MST in log-star rounds of congested clique
• Super-fast MST algorithms in the congested clique using \(o(m)\) messages

Cited In (4)

• Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
• A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem
• The Clustered Selected-Internal Steiner Tree Problem
• A distributed dual ascent algorithm for Steiner problems in multicast routing

Uses Software

• MapReduce

This page was built for publication: Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5859656)