Primal-dual based distributed approximation algorithm for prize-collecting Steiner tree. (English) Zbl 1476.90288
Summary: 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 et al., Math. Program. 59, No. 3 (A), 413–420 (1993; Zbl 0793.90089);
M. X. Goemans and D. P. Williamson, SIAM J. Comput. 24, No. 2, 296–317 (1995; Zbl 0834.68055);
D. S. Johnson et al., in: Proceedings of the 11th annual ACM-SIAM symposium on discrete algorithms, SODA 2000, San Francisco, CA, USA, January 9–11, 2000. Philadelphia, PA: SIAM. 760–769 (2000; Zbl 0956.68112);
A. Archer et al., SIAM J. Comput. 40, No. 2, 309–332 (2011; Zbl 1223.68125)]
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 \(\left(2-\frac{1}{n-1}\right)\) 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(mn)\), respectively, where \(n=|V|\) and \(m=|E|\). Furthermore, we modify the D-PCST algorithm and show that a \((2-\frac{1}{n-1})\)-approximate PCST can be deterministically computed using \(O(Dn)\) rounds and \(O(mn)\) 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(\Delta\log n)\) bits of memory in each node, where \(\Delta\) is the maximum degree of a node in the graph.
References:
| [1] | Agrawal, A., Klein, P. and Ravi, R., When trees collide: An approximation algorithm for the generalized Steiner problem on networks, SIAM J. Comput.24(3) (1995) 440-456. · Zbl 0831.68071 |
| [2] | Miranda, E. Álvarez, Candia, A., Chen, X., Hu, X. and Li, B., Efficient algorithms for the prize collecting Steiner tree problems with interval data, in Algorithmic Aspects in Information and Management, AAIM’10 (Weihai, China, 2010), pp. 13-24. · Zbl 1286.90154 |
| [3] | Miranda, E. Álvarez, Ljubić, I. and Toth, P., Exact approaches for solving robust prize-collecting Steiner tree problems, Eur. J. Oper. Res.229(3) (2013) 599-612. · Zbl 1317.90300 |
| [4] | Archer, A., Bateni, M. Hossein and Hajiaghayi, M. Taghi, Improved approximation algorithms for prize-collecting Steiner tree and TSP, SIAM J. Comput.40(2) (2011) 309-332. · Zbl 1223.68125 |
| [5] | Bacrach, N., Censor-Hillel, K., Dory, M., Efron, Y., Leitersdorf, D. and Paz, A., Hardness of distributed optimization, in Proc. 2019 ACM Symp. Principles of Distributed Computing, PODC ’19 (Toronto, Ontario, Canada, 2019), pp. 238-247. · Zbl 1542.68241 |
| [6] | Balas, E., The prize collecting traveling salesman problem, Networks19 (1989) 621-636. · Zbl 0676.90089 |
| [7] | Bar-Yehuda, R., Kantor, E., Kutten, S. and Rawitz, D., Growing half-balls: Minimizing storage and communication costs in CDNs, in Proc. 39th Int. Colloquium on Automata, Languages, and Programming, ICALP ’12 (Warwick, UK, 2012), pp. 416-427. · Zbl 1367.68016 |
| [8] | Bateni, M., Chekuri, C., Ene, A., Hajiaghayi, M. T., Korula, N. and Marx, D., Prize-collecting Steiner problems on planar graphs, in Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms, SODA ’11 (San Francisco, California, USA, 2011), pp. 1028-1049. · Zbl 1376.68059 |
| [9] | Bienstock, D., Goemans, M. X., Simchi-Levi, D. and Williamson, D., A note on the prize collecting traveling salesman problem. Math. Program.59 (1993) 413-420. · Zbl 0793.90089 |
| [10] | Byrka, J., Grandoni, F., Rothvoß, T. and Sanità, L., An improved LP-based approximation for Steiner tree, in Proc. Forty-Second ACM Symp. Theory of Computing, STOC ’10 (Cambridge, MA, USA, 2010), pp. 583-592. · Zbl 1293.05039 |
| [11] | Canuto, S. A., Resende, M. G. C. and Ribeiro, C. C., Local search with perturbation for prize-collecting Sreiner tree problem in graphs, Networks38(1) (2001) 50-58. · Zbl 1014.90078 |
| [12] | Chalermsook, P. and Fakcharoenphol, J., Simple distributed algorithms for approximating minimum Steiner trees, in Proc. 11th Annual Int. Conf. Computing and Combinatorics, COCOON’05 (Kunming, China, 2005), pp. 380-389. · Zbl 1128.68550 |
| [13] | Chen, G. H., Houle, M. E. and Kuo, M. T., The Steiner problem in distributed computing systems, Inf. Sci.74(1-2) (1993) 73-96. · Zbl 0783.68041 |
| [14] | Sarma, A. Das, Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D. and Wattenhofer, R., Distributed verification and hardness of distributed approximation, in Proc. Forty-Third Annual ACM Symp. Theory of Computing, STOC ’11 (San Jose, California, 2011), pp. 363-372. · Zbl 1288.68110 |
| [15] | Dittrich, M. T., Klau, G. W., Rosenwald, A., Dandekar, T. and Muller, T., Identifying functional modules in protein-protein interaction networks: An integrated exact approach. Intell. Syst. Mol. Biol.24(13) (2008) 119-141. |
| [16] | Elkin, M., An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem, SIAM J. Comput.36(2) (2006) 433-456. · Zbl 1116.05077 |
| [17] | Elkin, M., A simple deterministic distributed MST algorithm, with near-optimal time and message complexities, in Proc. ACM Symp. Principles of Distributed Computing, PODC ’17 (Washington, DC, USA, 2017), pp. 157-163. · Zbl 1380.68421 |
| [18] | Even, G., Ghaffari, M. and Medina, M., Distributed set cover approximation: Primal-dual with optimal locality, in 32nd Int. Symp. Distributed Computing, DISC 2018 (New Orleans, USA, 2018), pp. 22:1-22:14. · Zbl 1497.68561 |
| [19] | Feofiloff, P., Fernandes, C. G., Ferreira, C. E. and de Pina, J. Coelho, Primal-dual approximation algorithms for the prize-collecting Steiner tree problem, Inf. Process. Lett.103(5) (2007) 195-202. · Zbl 1184.68633 |
| [20] | Gallager, R. G., Humblet, P. A. and Spira, P. M., A distributed algorithm for minimum-weight spanning trees, ACM Trans. Program. Lang. Syst.1 (1983) 66-77. · Zbl 0498.68040 |
| [21] | Geunes, J., Levi, R., Romeijn, H. Edwin and Shmoys, D. B., Approximation algorithms for supply chain planning and logistics problems with market choice, Math. Program.130(1) (2011) 85-106. · Zbl 1229.90011 |
| [22] | Goemans, M. X. and Williamson, D. E., A general approximation technique for constrained forest problems, SIAM J. Appl. Math.24(2) (1995) 296-317. · Zbl 0834.68055 |
| [23] | Grandoni, F., Könemann, J., Panconesi, A. and Sozio, M., Primal-dual based distributed algorithms for vertex cover with semi-hard capacities, in Proc. Twenty-Fourth Annual ACM Symp. Principles of Distributed Computing, PODC ’05 (Las Vegas, Nevada, USA, 2005), pp. 118-125. · Zbl 1314.68156 |
| [24] | Grandoni, F., Könemann, J., Panconesi, A. and Sozio, M., A primal-dual bicriteria distributed algorithm for capacitated vertex cover, SIAM J. Comput.38(3) (2008) 825-840. · Zbl 1187.68707 |
| [25] | Haouari, M., Layeb, S. Bhar and Sherali, H. D., Algorithmic expedients for the prize collecting Steiner tree problem, Discrete Optim.7 (2010) 32-47. · Zbl 1271.90097 |
| [26] | Johnson, D. S., Minkoff, M. and Phillips, S., The prize collecting Steiner tree problem: Theory and practice, in Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA ’00 (San Francisco, California, 2000), pp. 760-769. · Zbl 0956.68112 |
| [27] | Karp, R. M., Reducibility among combinatorial problems, in Proc. Symp. Complexity of Computer Computations (Yorktown Heights, NY, USA, 1972), pp. 85-103. · Zbl 1467.68065 |
| [28] | Khan, M., Kuhn, F., Malkhi, D., Pandurangan, G. and Talwar, K., Efficient distributed approximation algorithms via probabilistic tree embeddings, in Proc. Twenty-Seventh ACM Symp. Principles of Distributed Computing, PODC ’08 (Toronto, Canada, 2008), pp. 263-272. · Zbl 1301.68257 |
| [29] | Khan, M. and Pandurangan, G., A fast distributed approximation algorithm for minimum spanning trees, Distrib. Comput.20(6) (2008) 391-402. · Zbl 1266.68214 |
| [30] | Klau, G. W., Ljubić, I., Moser, A., Mutzel, P., Neuner, P., Pferschy, U., Raidl, G. and Weiskircher, R., Combining a memetic algorithm with integer programming to solve the prize-collecting Steiner tree problem, in Genetic and Evolutionary Computation, GECCO ’04 (Seattle, Washington, USA, 2004), pp. 1304-1315. |
| [31] | Kutten, S., Pandurangan, G., Peleg, D., Robinson, P. and Trehan, A., On the complexity of universal leader election, J. ACM62(1) (2015) 7:1-7:27. · Zbl 1321.68285 |
| [32] | Lenzen, C. and Patt-Shamir, B., Improved distributed Steiner forest construction, in Proc. ACM Symp. Principles of Distributed Computing, PODC ’14 (Paris, France, 2014), pp. 262-271. · Zbl 1321.68481 |
| [33] | Lenzen, C. and Patt-Shamir, B., Fast partial distance estimation and applications, in Proc. 2015 ACM Symp. Principles of Distributed Computing, PODC ’15 (Donostia-San Sebastián, Spain, 2015), pp. 153-162. · Zbl 1333.68280 |
| [34] | Li, Y., Du, D., Xiu, N. and Xu, D., Improved approximation algorithms for the facility location problems with linear/submodular penalties, Algorithmica73(2) (2015) 460-482. · Zbl 1322.90045 |
| [35] | Ljubić, I., Weiskircher, R., Pferschy, U., Klau, G. W., Mutzel, P. and Fischetti, M., An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Math. Program. Series B105 (2006) 427-449. · Zbl 1085.90061 |
| [36] | Lu, C. Lung, Tang, C. Yi and Lee, R. ChiaTung, The full Steiner tree problem in phylogeny, in Int. Computing and Combinatorics Conf., COCOON’02 (Singapore, 2002), pp. 107-116. · Zbl 1077.68732 |
| [37] | Ma, C., Smith, V., Jaggi, M., Jordan, M. I., Richtárik, P. and Takáč, M., Adding vs. averaging in distributed primal-dual optimization, in Proc. 32nd Int. Conf. Machine Learning, ICML ’15 (Lille, France, 2015), pp. 1973-1982. |
| [38] | Moscibroda, T. and Wattenhofer, R., Facility location: Distributed approximation, in Proc. Twenty-Fourth Annual ACM Symp. Principles of Distributed Computing, PODC ’05 (Las Vegas, Nevada, USA, 2005) pp. 108-117. · Zbl 1314.68386 |
| [39] | Pandit, S. and Pemmaraju, S., Return of the primal-dual: Distributed metric facility location, in Proc. 28th ACM Symp. Principles of Distributed Computing, PODC ’09 (Calgary, Alberta, Canada, 2009), pp. 180-189. · Zbl 1291.90117 |
| [40] | Peleg, D., Distributed Computing: A Locality-Sensitive Approach (Society for Industrial and Applied Mathematics, 2000). · Zbl 0959.68042 |
| [41] | Peleg, D. and Rubinovich, V., A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction, SIAM J. Comput.30(5) (2000) 1427-1442. · Zbl 0973.05074 |
| [42] | Prodon, A., DeNegre, S. and Liebling, T. M., Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems, Math. Program.124(1) (2010) 119-141. · Zbl 1198.90341 |
| [43] | N. G. Rossetti, A first attempt on the distributed prize-collecting Steiner tree problem, M.Sc. thesis, University of Iceland, Reykjavik (2015). |
| [44] | Saikia, P. and Karmakar, S., A simple \(2(1-1/\ell)\) factor distributed approximation algorithm for Steiner tree in the CONGEST model, in Proc. 20th Int. Conf. Distributed Computing and Networking, ICDCN ’19 (Bangalore, India, 2019), pp. 41-50. |
| [45] | Wald, J. A. and Colbourn, C. J., Steiner trees, partial 2 — Trees, and minimum IFI networks, Networks13 (1983) 159-167. · Zbl 0529.68036 |
| [46] | Yuan, D., Xu, S. and Zhao, H., Distributed primal-dual subgradient method for multiagent optimization via consensus algorithms, IEEE Trans. Syst. Man Cybern. B Cybern.41(6) (2011) 1715-1724. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
