|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'928
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A Primal-Dual based Distributed Approximation Algorithm for Prize Collecting Steiner Tree | | Parikshit Saikia
; Sushanta Karmakar
; | | Date: |
19 Oct 2017 | | Abstract: | Constructing a steiner tree of a graph is a fundamental problem in many
applications. Prize collecting steiner tree (PCST) is a special variant of the
steiner tree problem and has applications in network design, content
distribution etc. There are a few centralized approximation algorithms
cite{DB_MG_DS_DW_1993, GW_1995, AA_MB_MH_2011} for solving the PCST problem.
However no distributed algorithm is known that solves the PCST problem with
non-trivial approximation factor. In this work we present a distributed
algorithm that constructs a prize collecting steiner tree for a given connected
undirected graph with non-negative weight for each edge and non-negative prize
value for each node. Initially each node knows its own prize value and weight
of each incident edge. Our algorithm is based on primal-dual method and it
achieves an approximation factor of $(2 - frac{1}{n - 1})$ of the optimal. The
total number of messages required by our distributed algorithm to construct the
PCST for a graph with $|V|$ nodes and $|E|$ edges is $O(|V|^2 + |E||V|)$. The
algorithm is spontaneously initiated at a special node called the root node and
when the algorithm terminates each node knows whether it is in the prize part
or in the steiner tree of the PCST. | | Source: | arXiv, 1710.7040 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER