Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
From MaRDI portal
Publication:5012805
DOI10.1142/S1793830921500087zbMath1476.90288arXiv1710.07040OpenAlexW3049110439MaRDI QIDQ5012805
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
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for supply chain planning and logistics problems with market choice
- A note on the prize collecting traveling salesman problem
- Improved approximation algorithms for the facility location problems with linear/submodular penalties
- The Steiner problem in distributed computing systems
- Algorithmic expedients for the prize collecting Steiner tree problem
- A fast distributed approximation algorithm for minimum spanning trees
- Exact approaches for solving robust prize-collecting Steiner tree problems
- Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
- An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
- Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems
- A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
- Local search with perturbations for the prize-collecting Steiner tree problem in graphs
- Fast Partial Distance Estimation and Applications
- An improved LP-based approximation for steiner tree
- Improved distributed steiner forest construction
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
- Growing Half-Balls: Minimizing Storage and Communication Costs in CDNs
- Steiner trees, partial 2–trees, and minimum IFI networks
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Efficient Algorithms for the Prize Collecting Steiner Tree Problems with Interval Data
- A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover
- The prize collecting traveling salesman problem
- A Distributed Algorithm for Minimum-Weight Spanning Trees
- Distributed Computing: A Locality-Sensitive Approach
- A General Approximation Technique for Constrained Forest Problems
- When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
- Reducibility among Combinatorial Problems
- Distributed set cover approximation: Primal-dual with optimal locality
- A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
- Hardness of Distributed Optimization
- Return of the primal-dual
- Facility location
- Primal-dual based distributed algorithms for vertex cover with semi-hard capacities
- Distributed verification and hardness of distributed approximation
- On the Complexity of Universal Leader Election
- Computing and Combinatorics
- Efficient distributed approximation algorithms via probabilistic tree embeddings
This page was built for publication: Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree
