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

DOI10.1142/S1793830921500087zbMATH Open1476.90288arXiv1710.07040OpenAlexW3049110439MaRDI QIDQ5012805FDOQ5012805

Authors: Parikshit Saikia, Sushanta Karmakar, Aris Pagourtzis 

Publication date: 25 November 2021

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

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.

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

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

zbMATH Keywords

primal-dual methoddistributed approximationprize-collecting Steiner tree

Mathematics Subject Classification ID

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

Cites Work

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

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)