{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:09:55Z","timestamp":1725516595022},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540850960"},{"type":"electronic","value":"9783540850977"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-85097-7_23","type":"book-chapter","created":{"date-parts":[[2008,8,19]],"date-time":"2008-08-19T03:18:26Z","timestamp":1219115906000},"page":"246-254","source":"Crossref","is-referenced-by-count":2,"title":["Elementary Approximation Algorithms for Prize Collecting Steiner Tree Problems"],"prefix":"10.1007","author":[{"given":"Shai","family":"Gutner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"23_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 Journal on Computing\u00a024(3), 440\u2013456 (1995)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"23_CR2","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy, A., Bar-Yehuda, R., Freund, A. (Seffi) Naor, J., Schieber, B.: A unified approach to approximating resource allocation and scheduling. Journal of the ACM\u00a048(5), 1069\u20131090 (2001)","journal-title":"Journal of the ACM"},{"issue":"2","key":"23_CR3","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"Bar-Yehuda, R.: One for the price of two: a unified approach for approximating covering problems. Algorithmica\u00a027(2), 131\u2013144 (2000)","journal-title":"Algorithmica"},{"issue":"4","key":"23_CR4","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1145\/1041680.1041683","volume":"36","author":"R. Bar-Yehuda","year":"2004","unstructured":"Bar-Yehuda, R., Bendel, K., Freund, A., Rawitz, D.: Local ratio: A unified framework for approximation algorithms: In memoriam: Shimon Even 1935\u20132004. ACM Computing Surveys\u00a036(4), 422\u2013463 (2004)","journal-title":"ACM Computing Surveys"},{"issue":"3","key":"23_CR5","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1137\/050625382","volume":"19","author":"R. Bar-Yehuda","year":"2005","unstructured":"Bar-Yehuda, R., Rawitz, D.: On the equivalence between the primal-dual schema and the local ratio technique. SIAM Journal on Discrete Mathematics\u00a019(3), 762\u2013797 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"23_CR6","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.\u00a059, 413\u2013420 (1993)","journal-title":"Math. Program."},{"issue":"2","key":"23_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 Journal on Computing\u00a024(2), 296\u2013317 (1995)","journal-title":"SIAM Journal on Computing"},{"key":"23_CR8","unstructured":"Gupta, A., K\u00f6nemann, J., Leonardi, S., Ravi, R., Sch\u00e4fer, G.: An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1153\u20131162 (2007)"},{"key":"23_CR9","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"23_CR10","unstructured":"Hayrapetyan, A., Swamy, C., Tardos, \u00c9.: Network design for information networks. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 933\u2013942 (2005)"},{"key":"23_CR11","unstructured":"Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting Steiner tree problem: theory and practice. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 760\u2013769 (2000)"},{"key":"23_CR12","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G.: A group-strategyproof mechanism for Steiner forests. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 612\u2013619 (2005)"},{"key":"23_CR13","unstructured":"Sharma, Y., Swamy, C., Williamson, D.P.: Approximation algorithms for prize-collecting forest problems with submodular penalty functions. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1275\u20131284 (2007)"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85097-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:41:01Z","timestamp":1619509261000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85097-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540850960","9783540850977"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85097-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}