Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

DOI10.1142/S1793830921500087MaRDI QIDQ5012805zbMATH OpenOpenAlexFDO

Authors Parikshit Saikia, Sushanta Karmakar, Aris Pagourtzis

Publication date 25 November 2021

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

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

zbMATH Keywords

primal-dual methoddistributed approximationprize-collecting Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Abstract: The Prize-Collecting Steiner Tree (PCST) problem is a generalization of the Steiner Tree problem that has applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms cite{DB_MG_DS_DW_1993, GW_1995, DJ_MM_SP_2000, AA_MB_MH_2011} for solving the PCST problem. However no distributed algorithm is known that solves PCST with a guaranteed approximation factor. In this work we present an asynchronous distributed $(2-frac1n-1)$-approximation algorithm that constructs a PCST for a given connected undirected graph with non-negative edge weights and a non-negative prize value for each node. Our algorithm is an adaptation of the centralized algorithm proposed by Goemans and Williamson cite{GW_1995} to the distributed setting, and is based on the primal-dual method. The message complexity of the algorithm with input graph having node set $V$ and edge set $E$ is $O(|V||E|)$. Initially each node knows only its own prize value and the weight of each incident edge. The algorithm is spontaneously initiated at a special node called the emph{root node} and when it terminates each node knows whether it is in the PCST or not. To the best of our knowledge this is the first distributed constant approximation algorithm for PCST.

Recommendations

• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• A Distributed Primal-Dual Heuristic for Steiner Problems in Networks
• A primal-dual algorithm for the generalized prize-collecting Steiner forest problem
• Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems
• Elementary approximation algorithms for prize collecting Steiner tree problems
• A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems
• A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem
• Distributed approximation algorithms for Steiner tree in the CONGESTED CLIQUE
• The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches
• Algorithmic expedients for the prize collecting Steiner tree problem

Cites work

• scientific article; zbMATH DE number 2089965 (Why is no real title available?)
• scientific article; zbMATH DE number 1445375 (Why is no real title available?)
• scientific article; zbMATH DE number 6783450 (Why is no real title available?)
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• A General Approximation Technique for Constrained Forest Problems
• A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
• A fast distributed approximation algorithm for minimum spanning trees
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• A note on the prize collecting traveling salesman problem
• Algorithmic expedients for the prize collecting Steiner tree problem
• An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An improved LP-based approximation for Steiner tree
• Approximation algorithms for supply chain planning and logistics problems with market choice
• Computing and Combinatorics
• Distributed Computing: A Locality-Sensitive Approach
• Distributed set cover approximation: primal-dual with optimal locality
• Distributed verification and hardness of distributed approximation
• Efficient algorithms for the prize collecting Steiner tree problems with interval data
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Exact approaches for solving robust prize-collecting Steiner tree problems
• Facility location, distributed approximation
• Fast partial distance estimation and applications
• Growing half-balls: minimizing storage and communication costs in CDNs
• Hardness of Distributed Optimization
• Improved approximation algorithms for prize-collecting Steiner tree and TSP
• Improved approximation algorithms for the facility location problems with linear/submodular penalties
• Improved distributed Steiner forest construction
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
• On the Complexity of Universal Leader Election
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
• Reducibility among combinatorial problems
• Return of the primal-dual, distributed metric facility location
• Steiner trees, partial 2–trees, and minimum IFI networks
• The Steiner problem in distributed computing systems
• The prize collecting traveling salesman problem
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks

Cited in

(2)

• A distributed dual ascent algorithm for the Hop-constrained Steiner tree problem
• A distributed dual ascent algorithm for Steiner problems in multicast routing

This page was built for publication: Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree

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