{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T15:43:18Z","timestamp":1709826198489},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p> Let G be a complete directed graph with n vertices and integer edge weights in range [0,M]. It is well known that an optimal Traveling Salesman Problem (TSP) in G can be solved in 2<jats:sup>n<\/jats:sup> time and space (all bounds are given within a polynomial factor of the input length, i.e., poly(n, log M)) and this is still the fastest known algorithm. If we allow a polynomial space only, then the best known algorithm has running time 4<jats:sup>n<\/jats:sup>n<jats:sup>log n<\/jats:sup>. For TSP with bounded weights there is an algorithm with 1.657<jats:sup>n<\/jats:sup> \u00b7 M running time. It is a big challenge to develop an algorithm with 2<jats:sup>n<\/jats:sup> time and polynomial space. Also, it is well-known that TSP cannot be approximated within any polynomial time computable function unless P=NP. <\/jats:p><jats:p> In this short note we propose a very simple algorithm that, for any 0 &lt; \u03b5 &lt; 1, finds (1+\u03b5)-approximation to asymmetric TSP in 2<jats:sup>n<\/jats:sup>\u03b5<jats:sup>\u22121<\/jats:sup> time and \u03b5<jats:sup>\u22121<\/jats:sup> \u00b7 poly(n, log M) space. Thereby, for any fixed \u03b5, the algorithm needs 2<jats:sup>n<\/jats:sup> steps and polynomial space to compute (1 + \u03b5)-approximation. <\/jats:p>","DOI":"10.1142\/s0129054114500051","type":"journal-article","created":{"date-parts":[[2014,4,29]],"date-time":"2014-04-29T02:35:13Z","timestamp":1398738913000},"page":"89-99","source":"Crossref","is-referenced-by-count":3,"title":["APPROXIMATING ASYMMETRIC TSP IN EXPONENTIAL TIME"],"prefix":"10.1142","volume":"25","author":[{"given":"ALEXANDER","family":"GOLOVNEV","sequence":"first","affiliation":[{"name":"Department of Computer Science, New York University, 251 Mercer St., New York, NY 10012, USA"}]}],"member":"219","published-online":{"date-parts":[[2014,4,28]]},"reference":[{"key":"p_3","first-page":"379","volume":"201","author":"Asadpour A.","journal-title":"PA, USA"},{"key":"p_5","volume":"60","author":"Bax E.","journal-title":"Inf. Process. Lett."},{"key":"p_8","first-page":"641","volume":"200","author":"Berman P.","journal-title":"NY, USA"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9149-8"},{"key":"p_12","first-page":"638","volume":"200","author":"Bl\u00e4ser M.","journal-title":"PA, USA"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1137\/0216034"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"p_23","volume":"22","author":"Ibarra O. H.","journal-title":"J. ACM"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"p_29","first-page":"484","volume":"201","author":"Koivisto M.","journal-title":"PA, USA"},{"key":"p_30","first-page":"321","volume":"201","author":"Lokshtanov D.","journal-title":"ACM"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"p_36","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114500051","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:46:18Z","timestamp":1565117178000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114500051"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":14,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2014,4,28]]},"published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1142\/S0129054114500051"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114500051","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}