乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T10:15:02Z","timestamp":1725531302966},"publisher-location":"Dordrecht","reference-count":28,"publisher":"Springer Netherlands","isbn-type":[{"type":"print","value":"9781402096877"},{"type":"electronic","value":"9781402096884"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-1-4020-9688-4_9","type":"book-chapter","created":{"date-parts":[[2009,4,20]],"date-time":"2009-04-20T06:15:15Z","timestamp":1240208115000},"page":"241-266","source":"Crossref","is-referenced-by-count":0,"title":["Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems"],"prefix":"10.1007","author":[{"given":"R.","family":"Ravi","sequence":"first","affiliation":[]},{"given":"Madhav V.","family":"Marathe","sequence":"additional","affiliation":[]},{"given":"S. S.","family":"Ravi","sequence":"additional","affiliation":[]},{"given":"Daniel J.","family":"Rosenkrantz","sequence":"additional","affiliation":[]},{"suffix":"III","given":"Harry B.","family":"Hunt","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A. Agrawal","year":"1995","unstructured":"A. Agrawal, P. Klein, and R. Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM J. Computing, 24:440\u2013456, 1995.","journal-title":"SIAM J. Computing"},{"key":"9_CR2","volume-title":"Network Flows: Theory and Algorithms","author":"R. Ahuja","year":"1993","unstructured":"R. Ahuja, T. Magnanti, and J. Orlin. Network Flows: Theory and Algorithms. Prentice Hall, Englewood Cliffs, 1993."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"S. Arora and M. Sudan. Improved low-degree testing and its applications. In Proc. 29th Annual ACM Symposium on Theory of Computing (STOC\u201997), pages 485\u2013496, 1997.","DOI":"10.1145\/258533.258642"},{"issue":"3","key":"9_CR4","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1016\/0167-8191(95)00010-0","volume":"22","author":"B. Boldon","year":"1996","unstructured":"B. Boldon, N. Deo, and N. Kumar. Minimum weight degree constrained spanning tree problem: Heuristics and implementation on a SIMD parallel machine. Parallel Computing, 22(3):369\u2013382, 1996.","journal-title":"Parallel Computing"},{"key":"9_CR5","volume-title":"LOVSZEM: Colloquium on the Theory of Algorithms","author":"P.\u00a0M. Camerini","year":"1985","unstructured":"P.\u00a0M. Camerini, G. Galbiati, and F. Maffioli. The complexity of weighted multi-constrained spanning tree problems. In LOVSZEM: Colloquium on the Theory of Algorithms. North-Holland, Amsterdam, 1985."},{"key":"9_CR6","series-title":"Wiley\u2013Interscience Series on Discrete Mathematics and Optimization","volume-title":"Combinatorial Optimization","author":"W. Cook","year":"1998","unstructured":"W. Cook, W. Cunningham, W. Pulleybank, and A. Schrijver. Combinatorial Optimization. Wiley\u2013Interscience Series on Discrete Mathematics and Optimization. Wiley, New York, 1998."},{"key":"9_CR7","volume-title":"Introduction to Algorithms","author":"T.\u00a0H. Cormen","year":"1990","unstructured":"T.\u00a0H. Cormen, C.\u00a0E. Leiserson, and R.\u00a0L. Rivest. Introduction to Algorithms. McGraw\u2013Hill, Cambridge, 1990."},{"key":"9_CR8","unstructured":"N. Deo and S.\u00a0L. Hakimi. The shortest generalized Hamiltonian tree. In Proc. 6th Annual Allerton Conference, pages 879\u2013888, 1968."},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1002\/net.3230170309","volume":"17","author":"C.\u00a0W. Duin","year":"1987","unstructured":"C.\u00a0W. Duin and A. Volgenant. Some generalizations of the Steiner problem in graphs. Networks, 17:353\u2013364, 1987.","journal-title":"Networks"},{"key":"9_CR10","volume-title":"Approximation Algorithms for NP-Hard Problems","author":"D. Hochbaum","year":"1997","unstructured":"D. Hochbaum (Editor). Approximation Algorithms for NP-Hard Problems. PWS, Boston, 1997."},{"issue":"2","key":"9_CR11","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1006\/jagm.1997.0862","volume":"24","author":"S. Fekete","year":"1997","unstructured":"S. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari, and N. Young. A\u00a0network flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms, 24(2):310\u2013324, 1997.","journal-title":"J. Algorithms"},{"key":"9_CR12","unstructured":"T. Fischer. Optimizing the degree of minimum weight spanning trees. Technical Report TR 93-1338, Department of Computer Science, Cornell University, Ithaca, New York, Apr. 1993."},{"issue":"3","key":"9_CR13","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1006\/jagm.1994.1042","volume":"17","author":"M. F\u00fcrer","year":"1994","unstructured":"M. F\u00fcrer and B. Raghavachari. Approximating the minimum-degree Steiner tree to within one of optimal. J. Algorithms, 17(3):409\u2013423, 1994.","journal-title":"J. Algorithms"},{"key":"9_CR14","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.\u00a0R. Garey","year":"1979","unstructured":"M.\u00a0R. Garey and D.\u00a0S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979."},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"M. Goemans","year":"1995","unstructured":"M. Goemans and D. Williamson. A general approximation technique for constrained forest problems. SIAM J. Computing, 24:296\u2013317, 1995.","journal-title":"SIAM J. Computing"},{"key":"9_CR16","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1002\/net.3230160209","volume":"16","author":"A. Iwainsky","year":"1986","unstructured":"A. Iwainsky, E. Canuto, O. Taraszow, and A. Villa. Network decomposition for the optimization of connection structures. Networks, 16:205\u2013235, 1986.","journal-title":"Networks"},{"issue":"2","key":"9_CR17","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1137\/S0097539794264585","volume":"25","author":"S. Khuller","year":"1996","unstructured":"S. Khuller, B. Raghavachari, and N. Young. Low-degree spanning trees of small weight. SIAM J. Computing, 25(2):355\u2013368, 1996.","journal-title":"SIAM J. Computing"},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1006\/jagm.1995.1029","volume":"19","author":"P. Klein","year":"1995","unstructured":"P. Klein and R. Ravi. A nearly best-possible approximation for node-weighted Steiner trees. J. Algorithms, 19(1):104\u2013115, 1995.","journal-title":"J. Algorithms"},{"issue":"6","key":"9_CR19","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1145\/331524.331526","volume":"46","author":"F.\u00a0T. Leighton","year":"1999","unstructured":"F.\u00a0T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with application to approximation algorithms. J. ACM, 46(6):787\u2013832, 1999.","journal-title":"J. ACM"},{"issue":"5","key":"9_CR20","doi-asserted-by":"publisher","first-page":"960","DOI":"10.1145\/185675.306789","volume":"41","author":"C. Lund","year":"1994","unstructured":"C. Lund and M. Yannakakis. On the hardness of approximating minimization problems. J. ACM, 41(5):960\u2013981, 1994.","journal-title":"J. ACM"},{"issue":"1","key":"9_CR21","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1006\/jagm.1998.0930","volume":"28","author":"M.\u00a0V. Marathe","year":"1998","unstructured":"M.\u00a0V. Marathe, R. Ravi, R. Sundaram, S.\u00a0S. Ravi, D.\u00a0J. Rosenkrantz, and H.\u00a0B. Hunt III. Bicriteria network design problems. J. Algorithms, 28(1):142\u2013171, 1998.","journal-title":"J. Algorithms"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF02293049","volume":"8","author":"C. Monma","year":"1992","unstructured":"C. Monma and S. Suri. Transitions in geometric minimum spanning trees. Discrete & Computational Geometry, 8(3):265\u2013293, 1992.","journal-title":"Discrete & Computational Geometry"},{"key":"9_CR23","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0196-6774(84)90029-4","volume":"4","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and U. Vazirani. On two geometric problems related to the traveling salesman problem. J. Algorithms, 4:231\u2013246, 1984.","journal-title":"J. Algorithms"},{"key":"9_CR24","unstructured":"R. Ravi. Rapid rumor ramification. In Proc. 35th Annual IEEE Symp. Foundations of Computer Science (FOCS\u201994), pages 202\u2013213, 1994."},{"key":"9_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/3-540-56287-7_112","volume-title":"Proc. 12th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST & TCS)","author":"R. Ravi","year":"1992","unstructured":"R. Ravi, B. Raghavachari, and P.\u00a0N. Klein. Approximation through local optimality: Designing networks with small degree. In Proc. 12th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FST & TCS). Lecture Notes in Computer Science, volume\u00a0652, pages\u00a0279\u2013290. Springer, Berlin, 1992."},{"key":"9_CR26","doi-asserted-by":"crossref","unstructured":"R. Ravi, M.\u00a0V. Marathe, S.\u00a0S. Ravi, D.\u00a0J. Rosenkrantz, and H.\u00a0B. Hunt III. Many birds with one stone: Multi-objective approximation algorithms. In Proc. 25th Annual ACM Symposium on Theory of Computing (STOC\u201993), pages 438\u2013447, 1993.","DOI":"10.1145\/167088.167209"},{"key":"9_CR27","doi-asserted-by":"crossref","unstructured":"R. Raz and S. Safra. A sub-constant error-probability low-degree test and a sub-constant error-probability PCP characterization of NP. In Proc. 29th Annual ACM Symposium on Theory of Computing (STOC\u201997), pages 475\u2013484, 1997.","DOI":"10.1145\/258533.258641"},{"issue":"3","key":"9_CR28","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D.\u00a0J. Rosenkrantz","year":"1977","unstructured":"D.\u00a0J. Rosenkrantz, R.\u00a0E. Stearns, and P.\u00a0M. Lewis\u00a0II. An analysis of several heuristics for the traveling salesman problem. SIAM J. Computing, 6(3):563\u2013581, 1977.","journal-title":"SIAM J. Computing"}],"container-title":["Fundamental Problems in Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-1-4020-9688-4_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,29]],"date-time":"2020-01-29T14:15:53Z","timestamp":1580307353000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-1-4020-9688-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9781402096877","9781402096884"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-1-4020-9688-4_9","relation":{},"subject":[],"published":{"date-parts":[[2009]]}}}