{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T04:34:26Z","timestamp":1649133266829},"reference-count":45,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:p> 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\u2013420; M. X. Goemans and D. E. Williamson, A general approximation technique for constrained forest problems, SIAM J. Appl. Math. 24(2) (1995) 296\u2013317; 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 \u201900 (2000), pp. 760\u2013769; 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\u2013332] 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 [Formula: see text] factor distributed approximation algorithm (D-PCST algorithm) that constructs a PCST for a given connected undirected graph of [Formula: see text] 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 [Formula: see text], the round and message complexities of the D-PCST algorithm in the CONGEST model are [Formula: see text] and [Formula: see text] respectively, where [Formula: see text] and [Formula: see text]. Furthermore, we modify the D-PCST algorithm and show that a [Formula: see text]-approximate PCST can be deterministically computed using [Formula: see text] rounds and [Formula: see text] messages in the CONGEST model, where [Formula: see text] is the unweighted diameter of [Formula: see text]. For networks with [Formula: see text], the modified D-PCST algorithm performs better than the original one in terms of the round complexity. Both the algorithms require [Formula: see text] bits of memory in each node, where [Formula: see text] is the maximum degree of a node in the graph. <\/jats:p>","DOI":"10.1142\/s1793830921500087","type":"journal-article","created":{"date-parts":[[2020,8,16]],"date-time":"2020-08-16T10:14:49Z","timestamp":1597572889000},"page":"2150008","source":"Crossref","is-referenced-by-count":1,"title":["Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree"],"prefix":"10.1142","volume":"13","author":[{"given":"Parikshit","family":"Saikia","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India"}]},{"given":"Sushanta","family":"Karmakar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, 781039 India"}]},{"given":"Aris","family":"Pagourtzis","sequence":"additional","affiliation":[{"name":"National Technical University of Athens, School of Electrical and Computer Engineering, Department of Computer Science, Heroon Politechniou, 9 GR-15780 Zographou, Greece"}]}],"member":"219","published-online":{"date-parts":[[2020,9,26]]},"reference":[{"issue":"3","key":"S1793830921500087BIB001","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"Agrawal A.","year":"1995","journal-title":"SIAM J. Comput."},{"key":"S1793830921500087BIB002","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-642-14355-7_3","volume-title":"Algorithmic Aspects in Information and Management, AAIM\u201910","author":"Miranda E. \u00c1lvarez","year":"2010"},{"issue":"3","key":"S1793830921500087BIB003","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1016\/j.ejor.2013.03.037","volume":"229","author":"Miranda E. \u00c1lvarez","year":"2013","journal-title":"Eur. J. Oper. Res."},{"issue":"2","key":"S1793830921500087BIB004","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"Archer A.","year":"2011","journal-title":"SIAM J. Comput."},{"key":"S1793830921500087BIB005","first-page":"238","volume-title":"Proc. 2019 ACM Symp. Principles of Distributed Computing, PODC \u201919","author":"Bacrach N.","year":"2019"},{"key":"S1793830921500087BIB006","doi-asserted-by":"crossref","first-page":"621","DOI":"10.1002\/net.3230190602","volume":"19","author":"Balas E.","year":"1989","journal-title":"Networks"},{"key":"S1793830921500087BIB007","doi-asserted-by":"crossref","first-page":"416","DOI":"10.1007\/978-3-642-31585-5_38","volume-title":"Proc. 39th Int. Colloquium on Automata, Languages, and Programming, ICALP \u201912","author":"Bar-Yehuda R.","year":"2012"},{"key":"S1793830921500087BIB008","first-page":"1028","volume-title":"Proc. Twenty-Second Annual ACM-SIAM Symp. Discrete Algorithms, SODA \u201911","author":"Bateni M.","year":"2011"},{"key":"S1793830921500087BIB009","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"Bienstock D.","year":"1993","journal-title":"Math. Program."},{"key":"S1793830921500087BIB010","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/1806689.1806769","volume-title":"Proc. Forty-Second ACM Symp. Theory of Computing, STOC \u201910","author":"Byrka J.","year":"2010"},{"issue":"1","key":"S1793830921500087BIB011","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1002\/net.1023","volume":"38","author":"Canuto S. A.","year":"2001","journal-title":"Networks"},{"key":"S1793830921500087BIB012","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1007\/11533719_39","volume-title":"Proc. 11th Annual Int. Conf. Computing and Combinatorics, COCOON\u201905","author":"Chalermsook P.","year":"2005"},{"issue":"1","key":"S1793830921500087BIB013","first-page":"73","volume":"74","author":"Chen G. H.","year":"1993","journal-title":"Inf. Sci."},{"key":"S1793830921500087BIB014","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1145\/1993636.1993686","volume-title":"Proc. Forty-Third Annual ACM Symp. Theory of Computing, STOC \u201911","author":"Sarma A. Das","year":"2011"},{"issue":"13","key":"S1793830921500087BIB015","first-page":"119","volume":"24","author":"Dittrich M. T.","year":"2008","journal-title":"Intell. Syst. Mol. Biol."},{"issue":"2","key":"S1793830921500087BIB016","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1137\/S0097539704441058","volume":"36","author":"Elkin M.","year":"2006","journal-title":"SIAM J. Comput."},{"key":"S1793830921500087BIB017","first-page":"157","volume-title":"Proc. ACM Symp. Principles of Distributed Computing, PODC \u201917","author":"Elkin M.","year":"2017"},{"key":"S1793830921500087BIB018","first-page":"22:1","volume-title":"32nd Int. Symp. Distributed Computing, DISC 2018","author":"Even G.","year":"2018"},{"issue":"5","key":"S1793830921500087BIB019","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.ipl.2007.03.012","volume":"103","author":"Feofiloff P.","year":"2007","journal-title":"Inf. Process. Lett."},{"key":"S1793830921500087BIB020","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1145\/357195.357200","volume":"1","author":"Gallager R. G.","year":"1983","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"S1793830921500087BIB021","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/s10107-009-0310-9","volume":"130","author":"Geunes J.","year":"2011","journal-title":"Math. Program."},{"issue":"2","key":"S1793830921500087BIB022","first-page":"296","volume":"24","author":"Goemans M. X.","year":"1995","journal-title":"SIAM J. Appl. Math."},{"key":"S1793830921500087BIB023","first-page":"118","volume-title":"Proc. Twenty-Fourth Annual ACM Symp. Principles of Distributed Computing, PODC \u201905","author":"Grandoni F.","year":"2005"},{"issue":"3","key":"S1793830921500087BIB024","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/06065310X","volume":"38","author":"Grandoni F.","year":"2008","journal-title":"SIAM J. Comput."},{"key":"S1793830921500087BIB025","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.disopt.2010.01.001","volume":"7","author":"Haouari M.","year":"2010","journal-title":"Discrete Optim."},{"key":"S1793830921500087BIB026","first-page":"760","volume-title":"Proc. Eleventh Annual ACM-SIAM Symp. Discrete Algorithms, SODA \u201900","author":"Johnson D. S.","year":"2000"},{"key":"S1793830921500087BIB027","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Proc. Symp. Complexity of Computer Computations","author":"Karp R. M.","year":"1972"},{"key":"S1793830921500087BIB028","first-page":"263","volume-title":"Proc. Twenty-Seventh ACM Symp. Principles of Distributed Computing, PODC \u201908","author":"Khan M.","year":"2008"},{"issue":"6","key":"S1793830921500087BIB029","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/s00446-007-0047-8","volume":"20","author":"Khan M.","year":"2008","journal-title":"Distrib. Comput."},{"key":"S1793830921500087BIB030","doi-asserted-by":"crossref","first-page":"1304","DOI":"10.1007\/978-3-540-24854-5_125","volume-title":"Genetic and Evolutionary Computation, GECCO \u201904","author":"Klau G. W.","year":"2004"},{"issue":"1","key":"S1793830921500087BIB031","doi-asserted-by":"crossref","first-page":"7:1","DOI":"10.1145\/2699440","volume":"62","author":"Kutten S.","year":"2015","journal-title":"J. ACM"},{"key":"S1793830921500087BIB032","first-page":"262","volume-title":"Proc. ACM Symp. Principles of Distributed Computing, PODC \u201914","author":"Lenzen C.","year":"2014"},{"key":"S1793830921500087BIB033","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/2767386.2767398","volume-title":"Proc. 2015 ACM Symp. Principles of Distributed Computing, PODC \u201915","author":"Lenzen C.","year":"2015"},{"issue":"2","key":"S1793830921500087BIB034","doi-asserted-by":"crossref","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Li Y.","year":"2015","journal-title":"Algorithmica"},{"key":"S1793830921500087BIB035","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/s10107-005-0660-x","volume":"105","author":"Ljubi\u0107 I.","year":"2006","journal-title":"Math. Program. Series B"},{"key":"S1793830921500087BIB036","first-page":"107","volume-title":"Int. Computing and Combinatorics Conf., COCOON\u201902","author":"Lu C. Lung","year":"2002"},{"key":"S1793830921500087BIB037","first-page":"1973","volume-title":"Proc. 32nd Int. Conf. Machine Learning, ICML \u201915","author":"Ma C.","year":"2015"},{"key":"S1793830921500087BIB038","first-page":"108","volume-title":"Proc. Twenty-Fourth Annual ACM Symp. Principles of Distributed Computing, PODC \u201905","author":"Moscibroda T.","year":"2005"},{"key":"S1793830921500087BIB039","first-page":"180","volume-title":"Proc. 28th ACM Symp. Principles of Distributed Computing, PODC \u201909","author":"Pandit S.","year":"2009"},{"key":"S1793830921500087BIB040","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"Peleg D.","year":"2000"},{"issue":"5","key":"S1793830921500087BIB041","doi-asserted-by":"crossref","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"Peleg D.","year":"2000","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S1793830921500087BIB042","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s10107-010-0368-4","volume":"124","author":"Prodon A.","year":"2010","journal-title":"Math. Program."},{"key":"S1793830921500087BIB044","first-page":"41","volume-title":"Proc. 20th Int. Conf. Distributed Computing and Networking, ICDCN \u201919","author":"Saikia P.","year":"2019"},{"key":"S1793830921500087BIB045","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1002\/net.3230130202","volume":"13","author":"Wald J. A.","year":"1983","journal-title":"Networks"},{"issue":"6","key":"S1793830921500087BIB046","doi-asserted-by":"crossref","first-page":"1715","DOI":"10.1109\/TSMCB.2011.2160394","volume":"41","author":"Yuan D.","year":"2011","journal-title":"IEEE Trans. Syst. Man Cybern. B Cybern."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830921500087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,8]],"date-time":"2021-02-08T16:55:44Z","timestamp":1612803344000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830921500087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,26]]},"references-count":45,"journal-issue":{"issue":"02","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["10.1142\/S1793830921500087"],"URL":"https:\/\/doi.org\/10.1142\/s1793830921500087","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9,26]]}}}