{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:31:32Z","timestamp":1725517892967},"publisher-location":"Berlin, Heidelberg","reference-count":12,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540853626"},{"type":"electronic","value":"9783540853633"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"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":[[2008]]},"DOI":"10.1007\/978-3-540-85363-3_9","type":"book-chapter","created":{"date-parts":[[2008,8,27]],"date-time":"2008-08-27T15:29:28Z","timestamp":1219850968000},"page":"104-117","source":"Crossref","is-referenced-by-count":1,"title":["Efficient Algorithms for Fixed-Precision Instances of Bin Packing and Euclidean TSP"],"prefix":"10.1007","author":[{"given":"David R.","family":"Karger","sequence":"first","affiliation":[]},{"given":"Jacob","family":"Scott","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"9_CR1","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1287\/opre.49.5.771.10607","volume":"49","author":"R.K. Ahuja","year":"2001","unstructured":"Ahuja, R.K., Orlin, J.B.: Inverse Optimization. Operations Research\u00a049(5), 771\u2013783 (2001)","journal-title":"Operations Research"},{"issue":"5","key":"9_CR2","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 traveling salesman and other geometric problems. Journal of the ACM (JACM)\u00a045(5), 753\u2013782 (1998)","journal-title":"Journal of the ACM (JACM)"},{"issue":"3","key":"9_CR3","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/S0020-0190(97)00213-5","volume":"65","author":"R. Balasubramanian","year":"1998","unstructured":"Balasubramanian, R., Fellows, M.R., Raman, V.: An improved fixed-parameter algorithm for vertex cover. Information Processing Letters\u00a065(3), 163\u2013168 (1998)","journal-title":"Information Processing Letters"},{"key":"9_CR4","unstructured":"Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Symposium on new directions and recent results in algorithms and complexity, page 441 (1976)"},{"key":"9_CR5","unstructured":"Coffman Jr., E.G., Garey, M.R., Johnson, D.S.: Approximation algorithms for bin packing: a survey. In: Approximation algorithms for NP-hard problems, pp. 46\u201393 (1996)"},{"issue":"4","key":"9_CR6","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"Downey, R.G., Fellows, M.R.: Fixed-Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput.\u00a024(4), 873\u2013921 (1995)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"9_CR7","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02579456","volume":"1","author":"W. Fernandez de la Vega","year":"1981","unstructured":"Fernandez de la Vega, W., Lueker, G.S.: Bin packing can be solved within 1+ \u03b5 in linear time. Combinatorica\u00a01(4), 349\u2013355 (1981)","journal-title":"Combinatorica"},{"key":"9_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume":"43","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. Complexity of Computer Computations\u00a043, 85\u2013103 (1972)","journal-title":"Complexity of Computer Computations"},{"key":"9_CR9","unstructured":"Korte, B., Schrader, R.: On the Existence of fast Approximation Schemes (1982)"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Orlin, J.B., Schulz, A.S., Sengupta, S.: \u03b5-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract). In: ACM Symposium on Theory of Computing, pp. 565\u2013572 (2000)","DOI":"10.1145\/335305.335377"},{"key":"9_CR11","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","volume":"4","author":"C.H. Papadimitriou","year":"1977","unstructured":"Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theoretical Computer Science\u00a04, 237\u2013244 (1977)","journal-title":"Theoretical Computer Science"},{"key":"9_CR12","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-85363-3_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T11:34:25Z","timestamp":1558265665000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-85363-3_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540853626","9783540853633"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-85363-3_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}