{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T20:08:12Z","timestamp":1725566892028},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540282396"},{"type":"electronic","value":"9783540318743"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11538462_14","type":"book-chapter","created":{"date-parts":[[2010,9,28]],"date-time":"2010-09-28T04:13:22Z","timestamp":1285647202000},"page":"158-169","source":"Crossref","is-referenced-by-count":5,"title":["Approximation Algorithms for Network Design and Facility Location with Service Capacities"],"prefix":"10.1007","author":[{"given":"Jens","family":"Ma\u00dfberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean tsp and other geometric problems. Journal of the ACM\u00a045, 753\u2013782 (1998)","journal-title":"Journal of the ACM"},{"key":"14_CR2","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, CS-93-13, G.S.I.A., Carnegie Mellon University, Pittsburgh (1976)"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for a capacitated facility location problem. In: Proceedings of the 10th annual ACM-SIAM symposium on Discrete algorithms (SODA 1999), pp. 875\u2013876 (1999)","DOI":"10.1007\/3-540-48777-8_8"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"Du, D.-Z., Zhang, Y., Feng, Q.: On better heuristic for Euclidean Steiner minimum trees. In: 32nd Annual IEEE Symposium on Foundations of Computer Science, pp. 431\u2013439 (1991)","DOI":"10.1109\/SFCS.1991.185402"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1007\/978-3-540-45198-3_3","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"G. Even","year":"2003","unstructured":"Even, G., Garg, N., K\u00f6nemann, J., Ravi, R., Sinha, A.: Covering graphs using trees and stars. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 24\u201335. Springer, Heidelberg (2003)"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1137\/0132072","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing steiner minimal trees. SIAM Journal on Applied Mathematics\u00a032, 835\u2013859 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"826","DOI":"10.1137\/0132071","volume":"32","author":"M.R. Garey","year":"1977","unstructured":"Garey, M.R., Johnson, D.S.: The rectilinear steiner problem is np-complete. SIAM Journal on Applied Mathematics\u00a032, 826\u2013834 (1977)","journal-title":"SIAM Journal on Applied Mathematics"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1137\/0114025","volume":"14","author":"M. Hanan","year":"1966","unstructured":"Hanan, M.: On steiner\u2019s problem with rectilinear distance. SIAM Journal on Applied Mathematics\u00a014(2), 255\u2013265 (1966)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"14_CR9","first-page":"232","volume-title":"Proceedings of the 2003 IEEE\/ACM international conference on Computer-aided design (ICCAD 2003)","author":"S. Held","year":"2003","unstructured":"Held, S., Korte, B., Ma\u00dfberg, J., Ringe, M., Vygen, J.: Clock scheduling and clocktree construction for high performance asics. In: Proceedings of the 2003 IEEE\/ACM international conference on Computer-aided design (ICCAD 2003), pp. 232\u2013240. IEEE Computer Society, Los Alamitos (2003)"},{"key":"14_CR10","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1137\/0130013","volume":"30","author":"F.K. Hwang","year":"1976","unstructured":"Hwang, F.K.: On steiner minimal trees with rectilinear distance. SIAM Journal on Applied Mathematics\u00a030, 104\u2013114 (1976)","journal-title":"SIAM Journal on Applied Mathematics"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Karmarkar, N., Karp, R.M.: An efficient approximation scheme for the onedimensional bin packing problem. In: 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 312\u2013320 (1982)","DOI":"10.1109\/SFCS.1982.61"},{"key":"14_CR12","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum Press, New York (1972)"},{"key":"14_CR13","volume-title":"Combinatorial Optimization, Theory and Algorithms","author":"B. Korte","year":"2005","unstructured":"Korte, B., Vygen, J.: Combinatorial Optimization, Theory and Algorithms, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/978-3-540-45198-3_12","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Mahdian","year":"2003","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: A 2-approximation algorithm for the soft-capacitated facility location problem. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol.\u00a02764, pp. 129\u2013140. Springer, Heidelberg (2003)"},{"issue":"6","key":"14_CR15","first-page":"573","volume":"24","author":"A. Matsuyama","year":"1980","unstructured":"Matsuyama, A., Takahashi, H.: An approximate solution for the steiner problem in graphs. Mathematica Japonica\u00a024(6), 573\u2013577 (1980)","journal-title":"Mathematica Japonica"},{"key":"14_CR16","unstructured":"Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: Symposium on Discrete Algorithms, pp. 770\u2013779 (2000)"},{"key":"14_CR17","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/1520-6750(199406)41:4<579::AID-NAV3220410409>3.0.CO;2-G","volume":"41","author":"D. Simchi-Levi","year":"1994","unstructured":"Simchi-Levi, D.: New worst-case results for the bin-packing problem. Naval Research Logistics\u00a041, 579\u2013585 (1994)","journal-title":"Naval Research Logistics"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. SIAM monographs on discrete mathematics and applications (2002)","DOI":"10.1137\/1.9780898718515"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11538462_14.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:13:44Z","timestamp":1605644024000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11538462_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540282396","9783540318743"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/11538462_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}