{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T08:23:14Z","timestamp":1772785394542,"version":"3.50.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,11,4]],"date-time":"2017-11-04T00:00:00Z","timestamp":1509753600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["grant UMO-2013\/11\/B\/ST6\/01748"],"award-info":[{"award-number":["grant UMO-2013\/11\/B\/ST6\/01748"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,2]]},"DOI":"10.1007\/s00224-017-9818-1","type":"journal-article","created":{"date-parts":[[2017,11,4]],"date-time":"2017-11-04T00:36:36Z","timestamp":1509755796000},"page":"319-336","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Maximum ATSP with Weights Zero and One via Half-Edges"],"prefix":"10.1007","volume":"62","author":[{"given":"Katarzyna","family":"Paluch","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,4]]},"reference":[{"issue":"1","key":"9818_CR1","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/S0196-6774(03)00112-3","volume":"50","author":"M Bl\u00e4ser","year":"2004","unstructured":"Bl\u00e4ser, M.: An 8\/13-approximation algorithm for the asymmetric maximum TSP. J. Algorithms 50(1), 23\u201348 (2004)","journal-title":"J. Algorithms"},{"key":"9818_CR2","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M.: A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. APPROX-RANDOM. In: Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and the 8th International Workshop on Randomization and Computation, vol. 3122 of Lecture Notes in Computer Science, pp. 61\u201371. Springer (2004)","DOI":"10.1007\/978-3-540-27821-4_6"},{"key":"9818_CR3","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser, M., Siebert, B.: Computing cycle covers without short cycles. In: Proceedings of the 9th Annual European Symposium on Algorithms (ESA), Lecture Notes in Computing Science, vol. 2161, pp 369\u2013379, Springer (2001)","DOI":"10.1007\/3-540-44676-1_31"},{"issue":"4","key":"9818_CR4","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/1082036.1082041","volume":"52","author":"H Kaplan","year":"2005","unstructured":"Kaplan, H., Lewenstein, M., Shafrir, N., Sviridenko, M.: Approximation algorithms for asymmetric tsp by decomposing directed regular multigraphs. J. ACM 52(4), 602\u2013626 (2005). Preliminary version appeared in FOCS\u201903","journal-title":"J. ACM"},{"key":"9818_CR5","unstructured":"Karpinski, M., Schmied, R.: Improved inapproximability results for the shortest superstring and related problems. In: Proceedings of Nineteenth Computing: The Australasian Theory Symposium, CATS 2013, vol. 141 of CRPIT, pp. 27\u201336. Australian Computer Society (2013)"},{"key":"9818_CR6","doi-asserted-by":"crossref","unstructured":"Kosaraju, S. R., Park, J. K., Stein, C.: Long tours and short superstrings. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp 166\u2013177 (1994)","DOI":"10.1109\/SFCS.1994.365696"},{"issue":"2","key":"9818_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1137\/S0895480102402861","volume":"17","author":"M Lewenstein","year":"2003","unstructured":"Lewenstein, M., Sviridenko, M.: A 5\/8 approximation algorithm for the maximum asymmetric tsp. SIAM J. Discrete Math. 17(2), 237\u2013248 (2003)","journal-title":"SIAM J. Discrete Math."},{"key":"9818_CR8","doi-asserted-by":"crossref","unstructured":"Micali, S., Vazirani, V. V.: An O ( | V | | E | ) $O(\\sqrt {|V|} |E|)$ algorithm for finding maximum matching in general graphs. FOCS. In: Proceedings of the 21st Annual Symposium on Foundations of Computer Science, pp. 17\u201327. IEEE Computer Society (1980)","DOI":"10.1109\/SFCS.1980.12"},{"key":"9818_CR9","doi-asserted-by":"crossref","unstructured":"Paluch, K. E.: Maximum ATSP with weights zero and one via half-edges. In: Proceedings of the 13th International Workshop on Approximation and Online Algorithms (2015)","DOI":"10.1007\/978-3-319-28684-6_3"},{"key":"9818_CR10","unstructured":"Paluch, K. E., Elbassioni, K. M., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In: Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science, STACS\u20192012, Leibniz International Proceedings of Informatics, vol. 14, pp 501\u2013506 (2012)"},{"key":"9818_CR11","unstructured":"Paluch, K.: Better approximation algorithms for maximum asymmetric traveling salesman and shortest superstring. arXiv: 1401.3670 (2014)"},{"key":"9818_CR12","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/0020-0190(92)90103-3","volume":"44","author":"S Vishwanathan","year":"1992","unstructured":"Vishwanathan, S.: An approximation algorithm for the asymmetric travelling salesman problem with distances one and two. Inform. Proc. Lett. 44, 297\u2013302 (1992)","journal-title":"Inform. Proc. Lett."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9818-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9818-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9818-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T11:54:09Z","timestamp":1570276449000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9818-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,4]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["9818"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9818-1","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,4]]}}}