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

The Prize-collecting Steiner tree (PCST) problem is a generalization of the Steiner tree problem that finds applications in network design, content distribution networks, and many more. There are a few centralized approximation algorithms [D. Bienstock, M. X. Goemans, D. Simchi-Levi and D. Williamson, A note on the prize collecting traveling salesman problem. Math. Program.59 (1993) 413–420; M. X. Goemans and D. E. Williamson, A general approximation technique for constrained forest problems, SIAM J. Appl. Math.24(2) (1995) 296–317; D. S. Johnson, M. Minkoff and S. Phillips, The prize collecting Steiner tree problem: Theory and practice, in Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA '00 (2000), pp. 760–769; A. Archer, M. Hossein Bateni and M. Taghi Hajiaghayi, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Comput.40(2) (2011) 309–332] for solving the PCST problem. However, the problem has seen very little progress in the distributed setting; to the best of our knowledge, the only distributed algorithms proposed so far are due to Rossetti [N. G. Rossetti, A first attempt on the distributed prize-collecting Steiner tree problem, M.Sc. thesis, University of Iceland, Reykjavik (2015)]: one of them fails to guarantee a constant approximation factor while the other one is essentially centralized. In this work, first, we present a deterministic 2 − 1 n − 1 factor distributed approximation algorithm (D-PCST algorithm) that constructs a PCST for a given connected undirected graph of n nodes with non-negative edge weights and non-negative prize value for each node. The D-PCST algorithm is based on the primal-dual method and uses a technique of preserving dual constraints in a distributed manner, without relying on knowledge of the global structure of the network. For an input graph G = (V , E) , the round and message complexities of the D-PCST algorithm in the CONGEST model are O (n 2) and O (m n) , respectively, where n = | V | and m = | E |. Furthermore, we modify the D-PCST algorithm and show that a (2 − 1 n − 1) -approximate PCST can be deterministically computed using O (D n) rounds and O (m n) messages in the CONGEST model, where D is the unweighted diameter of G. For networks with D = o (n) , the modified D-PCST algorithm performs better than the original one in terms of the round complexity. Both the algorithms require O (Δ log n) bits of memory in each node, where Δ is the maximum degree of a node in the graph. [ABSTRACT FROM AUTHOR]