{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:52Z","timestamp":1725795892151},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_48","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"576-587","source":"Crossref","is-referenced-by-count":11,"title":["Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems"],"prefix":"10.1007","author":[{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"first","affiliation":[]},{"given":"Vahid","family":"Liaghat","sequence":"additional","affiliation":[]},{"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"48_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized steiner problem on networks. In: STOC, pp. 134\u2013144 (1991)","DOI":"10.1145\/103418.103437"},{"issue":"2","key":"48_CR2","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.\u00a039(2), 361\u2013370 (2009)","journal-title":"SIAM J. Comput."},{"issue":"2-3","key":"48_CR3","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.\u00a0324(2-3), 313\u2013324 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"48_CR4","doi-asserted-by":"crossref","unstructured":"Berman, P., Coulston, C.: On-line algorithms for steiner tree problems. In: STOC, pp. 344\u2013353 (1997)","DOI":"10.1145\/258533.258618"},{"issue":"2\u20133","key":"48_CR5","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1561\/0400000024","volume":"3","author":"Niv Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: The design of competitive online algorithms via a primal-dual approach. In: FOCS, pp. 93\u2013263 (2009)","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"issue":"2","key":"48_CR6","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1287\/moor.1080.0363","volume":"34","author":"N. Buchbinder","year":"2009","unstructured":"Buchbinder, N., Naor, J.: Online primal-dual algorithms for covering and packing problems. Math. Oper. Res.\u00a034(2), 270\u2013286 (2009)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"48_CR7","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M.X. Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput.\u00a024(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"48_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"436","DOI":"10.1007\/978-3-642-31594-7_37","volume-title":"Automata, Languages, and Programming","author":"A. Gupta","year":"2012","unstructured":"Gupta, A., Nagarajan, V.: Approximating Sparse Covering Integer Programs Online. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012, Part I. LNCS, vol.\u00a07391, pp. 436\u2013448. Springer, Heidelberg (2012)"},{"key":"48_CR9","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Liaghat, V., Panigrahi, D.: Online node-weighted steiner forest and extensions via disk paintings. In: FOCS, pp. 558\u2013567 (2013)","DOI":"10.1109\/FOCS.2013.66"},{"issue":"3","key":"48_CR10","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.\u00a04(3), 369\u2013384 (1991)","journal-title":"SIAM J. Discrete Math."},{"key":"48_CR11","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting steiner tree problem: theory and practice. In: SODA, pp. 760\u2013769 (2000)"},{"key":"48_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Sadeghabad, S.S., Sanit\u00e0, L.: An LMP O(logn)-approximation algorithm for node weighted prize collecting steiner tree. In: FOCS, pp. 568\u2013577 (2013)","DOI":"10.1109\/FOCS.2013.67"},{"key":"48_CR13","unstructured":"Korman, S.: On the use of randomization in the online set cover problem. M.S. thesis, Weizmann Institute of Science (2005)"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"Naor, J., Panigrahi, D., Singh, M.: Online node-weighted steiner tree and related problems. In: FOCS, pp. 210\u2013219 (2011)","DOI":"10.1109\/FOCS.2011.65"},{"key":"48_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-22006-7_4","volume-title":"Automata, Languages and Programming","author":"J. Qian","year":"2011","unstructured":"Qian, J., Williamson, D.P.: An o(logn)-competitive algorithm for online constrained forest problems. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol.\u00a06755, pp. 37\u201348. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_48","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,11]],"date-time":"2019-08-11T08:41:47Z","timestamp":1565512907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_48"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_48","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}