Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE

DOI10.1142/S0129054120500367zbMATH Open1458.68278OpenAlexW2966268726MaRDI 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)

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

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)

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.

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

Cites work

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

Cited in

(5)

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

Describes a project that uses

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)