{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T11:10:04Z","timestamp":1751368204029,"version":"3.41.0"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,12,1]],"date-time":"2002-12-01T00:00:00Z","timestamp":1038700800000},"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":["Journal of Global Optimization"],"published-print":{"date-parts":[[2002,12]]},"DOI":"10.1023\/a:1021298822593","type":"journal-article","created":{"date-parts":[[2003,3,21]],"date-time":"2003-03-21T00:56:49Z","timestamp":1048208209000},"page":"437-448","source":"Crossref","is-referenced-by-count":6,"title":["A Polynomial Time Approximation Scheme for the Grade of Service Steiner Minimum Tree Problem"],"prefix":"10.1007","volume":"24","author":[{"given":"Joonmo","family":"Kim","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihaela","family":"Cardei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ionut","family":"Cardei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohua","family":"Jia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"406813_CR1","doi-asserted-by":"crossref","unstructured":"Arora, S. (1996), Polynomial-Time Approximation Schemes for Euclidean TSP and other Geometric Problems, Proceedings of 37th IEEE Symposium on Foundations of Computer Science, pp. 2\u201312.","DOI":"10.1109\/SFCS.1996.548458"},{"key":"406813_CR2","doi-asserted-by":"crossref","unstructured":"Arora, S. (1997), Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems, Proceedings of 38th IEEE Symposium on Foundations of Computer Science, pp. 554\u2013563.","DOI":"10.1109\/SFCS.1997.646145"},{"key":"406813_CR3","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1287\/mnsc.40.7.846","volume":"40","author":"A. Balakrishnan","year":"1994","unstructured":"Balakrishnan, A., Magnanti, T.L. and Mirchandani, P. (1994), Modeling and Heuristic Worst-Case Performance Analysis of the Two-level Network Design Problem, Management Science 40, 846\u2013867.","journal-title":"Management Science"},{"key":"406813_CR4","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0020-0190(86)90062-1","volume":"22","author":"E.J. Cockayne","year":"1986","unstructured":"Cockayne, E.J. and Hewgill, D.E. (1986), Exact Computation of Steiner Minimal Trees in the Plane, Information Processing Letters 22, 151\u2013156.","journal-title":"Information Processing Letters"},{"key":"406813_CR5","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/BF01758759","volume":"7","author":"E.J. Cockayne","year":"1992","unstructured":"Cockayne, E.J. and Hewgill, D.E., (1992), Improved Computation of Plane Steiner Minimal Trees, Algorithmica 7, 219\u2013229.","journal-title":"Algorithmica"},{"key":"406813_CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-1-4757-3171-2_9","volume-title":"Advances in Steiner Trees","author":"C.J. Colbourn","year":"2000","unstructured":"Colbourn, C.J. and Xue, G. (2000), Grade of Service Steiner Trees on a Series-Parallel Network, in Du, D.Z. Smith, J.M. and Rubinstein, J.H. (eds)., Advances in Steiner Trees, Kluwer Academic Publishers, Dordrecht, pp. 163\u2013174."},{"key":"406813_CR7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/S0377-2217(86)80007-8","volume":"27","author":"J.R. Current","year":"1986","unstructured":"Current, J.R., Revelle, C.S. and Cohon, J.L. (1986), The hierarchical network design problem, European Journal of Operational Research 27, 57\u201366.","journal-title":"European Journal of Operational Research"},{"key":"406813_CR8","doi-asserted-by":"crossref","unstructured":"Du, D.Z. and Hwang, F.K. (1990), An Approach for Proving Lower Bounds: Solution of Gilbert-Pollak Conjecture on Steiner Ratio, Proceedings of IEEE 31st FOCS, 76\u201385.","DOI":"10.1109\/FSCS.1990.89526"},{"key":"406813_CR9","doi-asserted-by":"crossref","unstructured":"Du, D.Z., Lu, B., Ngo, H. and Pardalos, P.M. (2000), Steiner Tree Problems, manuscript.","DOI":"10.1007\/0-306-48332-7_489"},{"key":"406813_CR10","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/BF02071982","volume":"33","author":"C. Duin","year":"1991","unstructured":"Duin, C. and Volgenant, A. (1991), The Multi-weighted Steiner Tree Problem, Annals of Operations Research 33, 451\u2013469.","journal-title":"Annals of Operations Research"},{"key":"406813_CR11","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1997","unstructured":"Garey, M.R., Graham, R.L. and Johnson, D.S. (1997), The Complexity of Computing Steiner Minimal trees, SIAM Journal of Applied Mathematics 32, 835\u2013859.","journal-title":"SIAM Journal of Applied Mathematics"},{"key":"406813_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0116001","volume":"16","author":"E.N. Gilbert","year":"1968","unstructured":"Gilbert, E.N. and Pollack, H.O. (1968), Steiner Minimal Trees, SIAM Journal on Applied Mathematics 16, 1\u201329.","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"406813_CR13","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/BF02061658","volume":"33","author":"F.K. Hwang","year":"1991","unstructured":"Hwang, F.K. (1991), A Primer of the Euclidean Steiner Problem, Annals of Operations Research 33, 73\u201384.","journal-title":"Annals of Operations Research"},{"key":"406813_CR14","unstructured":"Hwang, F.K., Richard, D.S. and Winter, P. (1992), The Steiner Tree Problem, in Annals of Discrete Mathematics 53, North-Holland, Amsterdam. 448 J. KIM ET AL."},{"key":"406813_CR15","doi-asserted-by":"crossref","first-page":"143","DOI":"10.4153\/CMB-1961-016-2","volume":"4","author":"Z.A. Melzak","year":"1961","unstructured":"Melzak, Z.A. (1961), On the Problem of Steiner, Canadian Mathematics Bulletin 4, 143\u2013148.","journal-title":"Canadian Mathematics Bulletin"},{"key":"406813_CR16","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1287\/ijoc.8.3.202","volume":"8","author":"P. Mirchandani","year":"1996","unstructured":"Mirchandani, P. (1996), The Multi-tier Tree Problem, INFORMS Journal on Computing 8, 202\u2013218.","journal-title":"INFORMS Journal on Computing"},{"key":"406813_CR17","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1109\/12.663766","volume":"47","author":"M. Sarrafzadeh","year":"1998","unstructured":"Sarrafzadeh, M., Lin, W.-L. and Wong, C.K. (1998), Floating Steiner Trees, IEEE Transactions on Computers 47, 197\u2013211.","journal-title":"IEEE Transactions on Computers"},{"key":"406813_CR18","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0166-218X(96)00064-9","volume":"71","author":"M.J. Smith","year":"1997","unstructured":"Smith, M.J. and Toppur, B. (1997), Euclidean Steiner Minimal Trees, Minimum Energy Configurations, and the Embedding Problem of Weighted Graphs in E3, Discrete Applied Mathematics 71, 187\u2013215.","journal-title":"E3, Discrete Applied Mathematics"},{"key":"406813_CR19","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1002\/net.3230150305","volume":"15","author":"P. Winter","year":"1985","unstructured":"Winter, P. (1985), An Algorithm for the Steiner problem in the Euclidean Plane, Networks 15, 323\u2013345.","journal-title":"Networks"},{"key":"406813_CR20","unstructured":"Winter, P. and Zachariasen, M. (1996), Large Euclidean Steiner Minimum Trees in an Hour, Technical report 96\/34, http:\/\/www.diku.dk\/pawel\/publications.html."},{"key":"406813_CR21","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1002\/(SICI)1097-0037(199710)30:3<149::AID-NET1>3.0.CO;2-L","volume":"30","author":"P. Winter","year":"1998","unstructured":"Winter, P. and Zachariasen, M. (1998), Large Euclidean Steiner Minimum Trees: an improved exact algorithm, Networks 30, 149\u2013166.","journal-title":"Networks"},{"key":"406813_CR22","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1007\/s00453-001-0050-6","volume":"31","author":"G.L. Xue","year":"2001","unstructured":"Xue, G.L., Lin, G.H. and Du, D.Z. (2001), Grade of Service Steiner Minimum Trees in the Euclidean Plane, Algorithmica, 31, 479\u2013500.","journal-title":"Algorithmica"},{"key":"406813_CR23","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1007\/BF01187035","volume":"9","author":"A. Zelikovsky","year":"1993","unstructured":"Zelikovsky, A. (1993), An 11 6-Approximation Algorithm for the Network Steiner Problem, Algorithmica 9, 463\u2013470.","journal-title":"Algorithmica"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021298822593.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1023\/A:1021298822593\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1023\/A:1021298822593.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:48:21Z","timestamp":1751366901000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1023\/A:1021298822593"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,12]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2002,12]]}},"alternative-id":["406813"],"URL":"https:\/\/doi.org\/10.1023\/a:1021298822593","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2002,12]]}}}