{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T13:03:47Z","timestamp":1753275827154,"version":"3.41.0"},"reference-count":20,"publisher":"EDP Sciences","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"published-print":{"date-parts":[[2016,1]]},"DOI":"10.1051\/ro\/2015010","type":"journal-article","created":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T12:35:15Z","timestamp":1427891715000},"page":"39-46","source":"Crossref","is-referenced-by-count":3,"title":["The Prize-collecting Call Control Problem on Weighted Lines and Rings"],"prefix":"10.1051","volume":"50","author":[{"given":"Weidong","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianping","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Li","family":"Guan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yaomin","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2015,8,26]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Adamy U., Ambuhl C., Anand R.S. and Erlebach T., Call Control in Rings.Algorithmica47(2007) 217\u2013238.","DOI":"10.1007\/s00453-006-0187-4"},{"key":"R2","unstructured":"Archer A., Bateni M.H., Hajiaghayi M.T. and Karloff H., Improved approximation algorithms for prize-collecting Steiner tree and TSP.SIAM J. Comput.40(2011) 309\u2013332."},{"key":"R3","doi-asserted-by":"crossref","unstructured":"Azar Y. and Regev O., Combinatorial algorithms for the unsplittable flow problem.Algorithmica44(2006) 49\u201366.","DOI":"10.1007\/s00453-005-1172-z"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"N. Bansal, A. Chakrabarti, A. Epstein and B. Schieber, A quasi-PTAS for unsplittable flow on line graphs, inProc. of the thirty-eighth annual ACM Symposium on Theory of computing(STOC) (2006) 721\u2013729.","DOI":"10.1145\/1132516.1132617"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"Bansal N., Friggstad Z., Khandekar R. and Salavatipour M.R., A logarithmic approximation for unsplittable flow on line graphs.ACM Trans. Algorithms10(2014) article no. 1.","DOI":"10.1145\/2532645"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Bar-Noy A., Bar-Yehuda R., Freund A., Naor J. and Schieber B., A unified approach to approximating resource allocation and scheduling.J. ACM48(2001) 1069\u20131090.","DOI":"10.1145\/502102.502107"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Bateni, C. Chekuri, A. Ene, M.T. Hajiaghayi, N. Korula and D. Marx, Prize-collecting steiner problems on planar graphs, inProc. of the 22nd annual ACM-SIAM Symposium on Discrete Algorithms (SODA)(2011) 1028\u20131049.","DOI":"10.1137\/1.9781611973082.79"},{"key":"R8","unstructured":"Bonsma P., Schulz J. and Wiese A., A constant-factor approximation algorithm for unsplittable flow on paths.SIAM J. Comput.43(2014) 767\u2013799."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Carlisle M.C. and Lloyd E.L., On thek-coloring of intervals.Discrete Appl. Math.59(1995) 225\u2013235.","DOI":"10.1016\/0166-218X(95)80003-M"},{"key":"R10","unstructured":"Calinescu G., Chakrabarti A., Karloff H. and Rabani Y., An improved approximation algorithm for resource allocation.ACM Trans. on Algorithms7(2011) article no. 48."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"Chakrabarti A., Chekuri C., Kumar A. and Gupta A., Approximation algorithms for the unsplittable flow problem.Algorithmica47(2007) 53\u201378.","DOI":"10.1007\/s00453-006-1210-5"},{"key":"R12","unstructured":"Chekuri C., Mydlarz M. and Shepherd F.B., Multicommodity demand flow in a tree and packing integer programs.ACM Trans. Algorithms3(2007) article no. 27."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"C. Chekuri, A. Ene and N. Korula, Unsplittable flow in paths and trees and column-restricted packing integer programs, inProc. of APPROX-RANDOM(2009) 42\u201355.","DOI":"10.1007\/978-3-642-03685-9_4"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Costa M.C., Letocart L. and Roupin F., Minimal multicut and maximum integer multiflow: a survey.Eur. J. Oper. Res.162(2005) 55\u201369.","DOI":"10.1016\/j.ejor.2003.10.037"},{"key":"R15","unstructured":"K. Elbassioni, N. Garg, D. Gupta, A. Kumar, V. Narula and A. Pal, Approximation algorithms for the unsplittable flow problem on paths and trees.Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)(2012) 267\u2013275."},{"key":"R16","unstructured":"M.R. Garey and D.S. Johnson, Computer and Intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company. San Francisco (1979)."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Hassin R. and Or E., Min sum clustering with penalties.Eur. J. Oper. Res.206(2010) 547\u2013554.","DOI":"10.1016\/j.ejor.2010.03.004"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"Ibarra O.H., Kim C.E., Fast approximation algorithms for the knapsack and sum of subset problems.J. ACM22(1975) 463\u2013468.","DOI":"10.1145\/321906.321909"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"J.M. Kleinberg, Single-source unsplittable flow, inProc. of 37th Annual Symposium on Foundation of Computer Science(FOCS) (1996) 68\u201377.","DOI":"10.1109\/SFCS.1996.548465"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"W. Li, Y. Shi, Li. Guan and J. Li, The prize-collecting call control problem, inProc. of 2nd International Conference on Information Science and Engineering(2010) 1609\u20131612.","DOI":"10.1109\/ICISE.2010.5691199"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015010\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T19:55:08Z","timestamp":1747857308000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ro.org\/10.1051\/ro\/2015010"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,26]]},"references-count":20,"journal-issue":{"issue":"1"},"alternative-id":["ro150010"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2015010","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"1290-3868"}],"subject":[],"published":{"date-parts":[[2015,8,26]]}}}