{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:45Z","timestamp":1740109305916,"version":"3.37.3"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T00:00:00Z","timestamp":1638230400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T00:00:00Z","timestamp":1638230400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1585\/15"],"award-info":[{"award-number":["1585\/15"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2014414"],"award-info":[{"award-number":["2014414"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1817\/17"],"award-info":[{"award-number":["1817\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.022.211"],"award-info":[{"award-number":["639.022.211"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00453-021-00888-7","type":"journal-article","created":{"date-parts":[[2021,11,30]],"date-time":"2021-11-30T17:07:51Z","timestamp":1638292071000},"page":"304-324","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight Bounds for Online Weighted Tree Augmentation"],"prefix":"10.1007","volume":"84","author":[{"given":"Joseph","family":"Naor","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6984-4007","authenticated-orcid":false,"given":"Seeun William","family":"Umboh","sequence":"additional","affiliation":[]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,30]]},"reference":[{"issue":"2","key":"888_CR1","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1137\/060661946","volume":"39","author":"N Alon","year":"2009","unstructured":"Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., Naor, J.: The online set cover problem. SIAM J. Comput. 39(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"key":"888_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."},{"key":"888_CR3","doi-asserted-by":"crossref","unstructured":"Bartal, Y., Fandina, N., Umboh, S.W.: Online probabilistic metric embedding: a general framework for bypassing inherent bounds. In: Chawla, S. (eds) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, 5\u20138 Jan 2020, pp. 1538\u20131557. SIAM (2020)","DOI":"10.1137\/1.9781611975994.95"},{"key":"888_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":"888_CR5","unstructured":"Dehghani, S., Ehsani, S., Hajiaghayi, M.T., Liaghat, V., Seddighin, S.: Greedy algorithms for online survivable network design. In: 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, 9\u201313 July 2018, Prague, Czech Republic, pp. 152:1\u2013152:14 (2018)"},{"key":"888_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.dam.2014.06.019","volume":"178","author":"G Even","year":"2014","unstructured":"Even, G., Smorodinsky, S.: Hitting sets online and unique-max coloring. Discrete Appl. Math. 178, 71\u201382 (2014)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"888_CR7","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1137\/0210019","volume":"10","author":"GN Frederickson","year":"1981","unstructured":"Frederickson, G.N., J\u00e1J\u00e1, J.: Approximation algorithms for several graph augmentation problems. SIAM J. Comput. 10(2), 270\u2013283 (1981)","journal-title":"SIAM J. Comput."},{"key":"888_CR8","doi-asserted-by":"crossref","unstructured":"Golumbic, M.C.: Algorithmic graph theory and perfect graphs (1980)","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"888_CR9","doi-asserted-by":"crossref","unstructured":"Grandoni, F.., Kalaitzis, C., Zenklusen, R.: Improved approximation for tree augmentation: saving by rewiring. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25\u201329, 2018, pp. 632\u2013645 (2018)","DOI":"10.1145\/3188745.3188898"},{"issue":"6","key":"888_CR10","doi-asserted-by":"publisher","first-page":"1649","DOI":"10.1137\/09076725X","volume":"41","author":"A Gupta","year":"2012","unstructured":"Gupta, A., Krishnaswamy, R., Ravi, R.: Online and stochastic survivable network design. SIAM J. Comput. 41(6), 1649\u20131672 (2012)","journal-title":"SIAM J. Comput."},{"key":"888_CR11","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., 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":"888_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/978-3-662-43948-7_48","volume-title":"Automata, Languages, and Programming, 41st International Colloquium, ICALP 2014","author":"MT Hajiaghayi","year":"2014","unstructured":"Hajiaghayi, M.T., 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, Berlin (2014)"},{"key":"888_CR13","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."},{"issue":"70","key":"888_CR14","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1515\/crll.1869.70.185","volume":"1869","author":"Camille Jordan","year":"1869","unstructured":"Jordan, Camille: Sur les assemblages de lignes. J. Reine Angew. Math. 1869(70), 185\u2013190 (1869)","journal-title":"J. Reine Angew. Math."},{"key":"888_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511616655","volume-title":"A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics","author":"J Lee","year":"2004","unstructured":"Lee, J.: A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2004)"},{"key":"888_CR16","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: The parking permit problem. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pp. 274\u2013282 (2005)","DOI":"10.1109\/SFCS.2005.72"},{"key":"888_CR17","doi-asserted-by":"crossref","unstructured":"Naor, J., Panigrahi, D., Singh, M.: Online node-weighted Steiner tree and related problems. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 Oct 2011, pp. 210\u2013219 (2011)","DOI":"10.1109\/FOCS.2011.65"},{"key":"888_CR18","unstructured":"Naor, J.S., Umboh, S.W., Williamson, D.P.: Tight bounds for online weighted tree augmentation. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, 9\u201312 July 2019, Patras, Greece, LIPIcs, vol. 132, pp. 88:1\u201388:14. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, Wadern (2019)"},{"issue":"11","key":"888_CR19","doi-asserted-by":"publisher","first-page":"3335","DOI":"10.1007\/s00453-017-0391-4","volume":"80","author":"J Qian","year":"2018","unstructured":"Qian, J., Umboh, S.W., Williamson, D.P.: Online constrained forest and prize-collecting network design. Algorithmica 80(11), 3335\u20133364 (2018)","journal-title":"Algorithmica"},{"issue":"3","key":"888_CR20","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"key":"888_CR21","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"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00888-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00888-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00888-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T09:12:39Z","timestamp":1726218759000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00888-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,30]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["888"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00888-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,11,30]]},"assertion":[{"value":"25 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}