{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:31Z","timestamp":1725488611956},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_27","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"275-286","source":"Crossref","is-referenced-by-count":3,"title":["Differential Approximation Results for the Traveling Salesman Problem with Distances 1 and 2"],"prefix":"10.1007","author":[{"given":"J\u00e9r\u00f4me","family":"Monnot","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vangelis T.","family":"Paschos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sophie","family":"Toulouse","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"key":"27_CR1","unstructured":"A. Aiello, E. Burattini, M. Furnari, A. Massarotti, and F. Ventriglia. Computational complexity: the problem of approximation. In C. M. S. J. Bolyai, editor, Algebra, combinatorics, and logic in computer science, volume I, pages 51\u201362, New York, 1986. North-Holland."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1016\/0022-0000(80)90046-X","volume":"21","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. D\u2019Atri, and M. Protasi. Structure preserving reductions among convex optimization problems. J. Comput. System Sci., 21:136\u2013153, 1980.","journal-title":"J. Comput. System Sci."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0304-3975(80)90006-7","volume":"12","author":"G. Ausiello","year":"1980","unstructured":"G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi. Towards a unified approach for the classification of NP-complete optimization problems. Theoret. Comput. Sci., 12:83\u201396, 1980.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR4","first-page":"429","volume":"69","author":"M. Bellare","year":"1995","unstructured":"M. Bellare and P. Rogaway. The complexity of approximating a nonlinear program. Math. Programming, 69:429\u2013441, 1995.","journal-title":"Math. Programming"},{"issue":"8","key":"27_CR5","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1287\/mnsc.23.8.789","volume":"23","author":"G. Cornuejols","year":"1977","unstructured":"G. Cornuejols, M. L. Fisher, and G. L. Nemhauser. Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Management Science, 23(8):789\u2013810, 1977.","journal-title":"Management Science"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0304-3975(97)00099-6","volume":"209","author":"M. Demange","year":"1998","unstructured":"M. Demange, P. Grisoni, and V. T. Paschos. Differential approximation algorithms for some combinatorial optimization problems. Theoret. Comput. Sci., 209:107\u2013122, 1998.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR7","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(95)00060-7","volume":"158","author":"M. Demange","year":"1996","unstructured":"M. Demange and V. T. Paschos. On an approximation measure founded on the links between optimization and polynomial approximation theory. Theoret. Comput. Sci., 158:117\u2013141, 1996.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/3-540-49116-3_35","volume-title":"Proc. STACS\u201999","author":"L. Engebretsen","year":"1999","unstructured":"L. Engebretsen. An explicit lower bound for TSP with distances one and two. In Proc. STACS\u201999, volume 1563 of LNCS, pages 373\u2013382. Springer, 1999."},{"key":"27_CR9","volume-title":"Computers and intractability. A guide to the theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W. H. Freeman, San Francisco, 1979."},{"key":"27_CR10","unstructured":"D. B. Hartvigsen. Extensions of matching theory. PhD thesis, Carnegie-Mellon University, 1984."},{"key":"27_CR11","unstructured":"J. Monnot, V. T. Paschos, and S. Toulouse. Differential approximation results for the traveling salesman problem. Cahier du LAMSADE 172, LAMSADE, Universit\u00e9 Paris-Dauphine, 2000."},{"key":"27_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1287\/moor.18.1.1","volume":"18","author":"C. H. Papadimitriou","year":"1993","unstructured":"C. H. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Math. Oper. Res., 18:1\u201311, 1993.","journal-title":"Math. Oper. Res."},{"key":"27_CR13","first-page":"80","volume":"25","author":"A. I. Serdyukov","year":"1984","unstructured":"A. I. Serdyukov. An algorithm with an estimate for the traveling salesman problem of the maximum. Upravlyaemye Sistemy, 25:80\u201386, 1984.","journal-title":"Upravlyaemye Sistemy"},{"key":"27_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/BF01581085","volume":"57","author":"S. A. Vavasis","year":"1992","unstructured":"S. A. Vavasis. Approximation algorithms for indefinite quadratic programming. Math. Programming, 57:279\u2013311, 1992.","journal-title":"Math. Programming"},{"key":"27_CR15","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/moor.6.3.319","volume":"6","author":"E. Zemel","year":"1981","unstructured":"E. Zemel. Measuring the quality of approximate solutions to zero-one programming problems. Math. Oper. Res., 6:319\u2013332, 1981.","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,21]],"date-time":"2019-02-21T06:50:13Z","timestamp":1550731813000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}