{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:16:32Z","timestamp":1743081392618,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642392054"},{"type":"electronic","value":"9783642392061"}],"license":[{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2013,1,1]],"date-time":"2013-01-01T00:00:00Z","timestamp":1356998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-39206-1_8","type":"book-chapter","created":{"date-parts":[[2013,7,2]],"date-time":"2013-07-02T17:20:16Z","timestamp":1372785616000},"page":"81-92","source":"Crossref","is-referenced-by-count":11,"title":["Improved Approximation Algorithms for (Budgeted) Node-Weighted Steiner Problems"],"prefix":"10.1007","author":[{"given":"MohammadHossein","family":"Bateni","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MohammadTaghi","family":"Hajiaghayi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vahid","family":"Liaghat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_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 (1991)","DOI":"10.1145\/103418.103437"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/978-3-642-32512-0_9","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"C. Chekuri","year":"2012","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Prize-collecting survivable network design in node-weighted graphs. In: Gupta, A., Jansen, K., Rolim, J., Servedio, R. (eds.) APPROX\/RANDOM 2012. LNCS, vol.\u00a07408, pp. 98\u2013109. Springer, Heidelberg (2012)"},{"key":"8_CR3","unstructured":"Cheng, X., Li, Y., Du, D.-Z., Ngo, H.Q.: Steiner trees in industry. In: Handbook of Combinatorial Optimization (2005)"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1007\/s10107-003-0479-2","volume":"100","author":"F.A. Chudak","year":"2004","unstructured":"Chudak, F.A., Roughgarden, T., Williamson, D.P.: Approximate k-MSTs and k-Steiner trees via the primal-dual method and Lagrangean relaxation. Mathematical Programming\u00a0100, 411\u2013421 (2004)","journal-title":"Mathematical Programming"},{"key":"8_CR5","doi-asserted-by":"crossref","unstructured":"Erlebach, T., Grant, T., Kammer, F.: Maximising lifetime for fault-tolerant target coverage in sensor networks. In: SPAA (2011)","DOI":"10.1145\/1989493.1989521"},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1006\/jcss.2001.1754","volume":"63","author":"J. Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Papadimitriou, C.H., Shenker, S.: Sharing the cost of multicast transmissions. Journal of Computer and System Sciences\u00a063, 21\u201341 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"8_CR7","doi-asserted-by":"crossref","unstructured":"Garg, N.: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. In: STOC (2005)","DOI":"10.1145\/1060590.1060650"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. Goemans","year":"1992","unstructured":"Goemans, M., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. on Computing\u00a024, 296\u2013317 (1992)","journal-title":"SIAM J. on Computing"},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Guha, S., Moss, A., Naor, J(S.), Schieber, B.: Efficient recovery from power outage. In: STOC (1999)","DOI":"10.1145\/301250.301406"},{"key":"8_CR10","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation. J. ACM"},{"issue":"1","key":"8_CR11","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms\u00a019(1), 104\u2013115 (1995)","journal-title":"J. Algorithms"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Sadeghian, S., Sanita, L.: An LMP O(logn)-approximation algorithm for node weighted prize collecting Steiner tree (unpublished, 2013)","DOI":"10.1109\/FOCS.2013.67"},{"issue":"2","key":"8_CR13","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1137\/S0097539702420474","volume":"37","author":"A. Moss","year":"2007","unstructured":"Moss, A., Rabani, Y.: Approximation algorithms for constrained node weighted Steiner tree problems. SIAM J. Comput.\u00a037(2), 460\u2013481 (2007)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"8_CR14","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1137\/S0895480194266331","volume":"9","author":"R. Ravi","year":"1996","unstructured":"Ravi, R., Sundaram, R., Marathe, M.V., Rosenkrantz, D.J., Ravi, S.S.: Spanning trees - short or small. SIAM J. Discrete Math.\u00a09(2), 178\u2013200 (1996)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-39206-1_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,13]],"date-time":"2023-02-13T21:38:52Z","timestamp":1676324332000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-642-39206-1_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642392054","9783642392061"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-39206-1_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}