{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:34Z","timestamp":1740109294490,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T00:00:00Z","timestamp":1509321600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T00:00:00Z","timestamp":1509321600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1115256"],"award-info":[{"award-number":["1115256"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00453-017-0391-4","type":"journal-article","created":{"date-parts":[[2017,10,30]],"date-time":"2017-10-30T14:23:02Z","timestamp":1509373382000},"page":"3335-3364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Online Constrained Forest and Prize-Collecting Network Design"],"prefix":"10.1007","volume":"80","author":[{"given":"Jiawei","family":"Qian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2884-0058","authenticated-orcid":false,"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,30]]},"reference":[{"key":"391_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24, 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"key":"391_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1016\/j.tcs.2004.05.021","volume":"324","author":"B Awerbuch","year":"2004","unstructured":"Awerbuch, B., Azar, Y., Bartal, Y.: On-line generalized Steiner problem. Theor. Comput. Sci. 324, 313\u2013324 (2004)","journal-title":"Theor. Comput. Sci."},{"volume-title":"Network Models, Handbooks in Operations Research and Management Science","year":"1995","key":"391_CR3","unstructured":"Ball, M.O., Magnanti, T.L., Monma, C.L., Nemhauser, G.L. (eds.): Network Models, Handbooks in Operations Research and Management Science, vol. 7. Elsevier, Amsterdam (1995)"},{"key":"391_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorithms for Steiner tree problems. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"key":"391_CR5","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.P.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413\u2013420 (1993)","journal-title":"Math. Program."},{"key":"391_CR6","unstructured":"Cheung, S.S.: Offline and online facility location and network design. Ph.D. thesis, Cornell University, School of Operations Research and Information Engineering (2016)"},{"key":"391_CR7","unstructured":"Goemans, M., Goldberg, A., Plotkin, S., Shmoys, D., Tardos, E., Williamson, D.: Improved approximation algorithms for network design problems. In: Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms, pp. 223\u2013232 (1994)"},{"key":"391_CR8","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. In: Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 307\u2013316 (1992)"},{"key":"391_CR9","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24, 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"391_CR10","doi-asserted-by":"crossref","unstructured":"Gu, A., Gupta, A., Kumar, A.: The power of deferral: maintaining a constant competitive Steiner tree online. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing, pp. 525\u2013534 (2013)","DOI":"10.1145\/2488608.2488674"},{"key":"391_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Ravi, R.: Online and stochastic survivable network design. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 685\u2013694 (2009)","DOI":"10.1145\/1536414.1536507"},{"key":"391_CR12","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Jain, K.: Prize-collecting generalized Steiner tree problem via a new approach of primal\u2013dual schema. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"391_CR13","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Liaghat, V., Panigrahi, D.: Online node-weighted Steiner forest and extensions via disk paintings. In: Proceedings of the 54th Annual Symposium on Foundations of Computer Science, pp. 558\u2013567 (2013)","DOI":"10.1109\/FOCS.2013.66"},{"key":"391_CR14","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Liaghat, V., Panigrahi, D.: Near-optimal online algorithms for prize-collecting Steiner problems. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014, Lecture Notes in Computer Science, vol. 8572, pp. 576\u2013587. Springer (2014)","DOI":"10.1007\/978-3-662-43948-7_48"},{"key":"391_CR15","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 933\u2013942 (2005)"},{"key":"391_CR16","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/0404033","volume":"4","author":"M Imase","year":"1991","unstructured":"Imase, M., Waxman, B.M.: Dynamic Steiner tree problem. SIAM J. Discrete Math. 4, 369\u2013384 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"391_CR17","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proceedings of the 11th ACM-SIAM Symposium on Discrete Algorithms, pp. 760\u2013769 (2000)"},{"key":"391_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"391_CR19","doi-asserted-by":"crossref","unstructured":"Megow, N., Skutella, M., Verschae, J., Wiese, A.: The power of recourse for online MST and TSP. In: Czumaj, A., Mehlhorn, K., Pitts, A.M., Wattenhofer, R. (eds.) Automata, Languages, and Programming, no. 7391 in Lecture Notes in Computer Science, pp. 689\u2013700. Springer (2012)","DOI":"10.1007\/978-3-642-31594-7_58"},{"key":"391_CR20","doi-asserted-by":"crossref","unstructured":"Qian, J., Williamson, D.P.: An $${O}(\\log n)$$-competitive algorithm for online constrained forest problems. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) Automata, Languages, and Programming, no. 6755 in Lecture Notes in Computer Science, pp. 37\u201348. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-22006-7_4"},{"key":"391_CR21","unstructured":"Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize collecting forest problems with submodular penalty functions. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 1275\u20131284 (2007)"},{"key":"391_CR22","doi-asserted-by":"crossref","unstructured":"Umboh, S.: Online network design algorithms via hierarchical decompositions. In: Proceedings of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1373\u20131387 (2015)","DOI":"10.1137\/1.9781611973730.91"},{"key":"391_CR23","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/BF01299747","volume":"15","author":"DP Williamson","year":"1995","unstructured":"Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal\u2013dual approximation algorithm for generalized Steiner network problems. Combinatorica 15, 435\u2013454 (1995)","journal-title":"Combinatorica"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0391-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0391-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0391-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,17]],"date-time":"2020-05-17T06:30:34Z","timestamp":1589697034000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0391-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,30]]},"references-count":23,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["391"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0391-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,10,30]]},"assertion":[{"value":"22 December 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}