{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,5]],"date-time":"2026-05-05T18:29:25Z","timestamp":1778005765068,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2005,7,1]],"date-time":"2005-07-01T00:00:00Z","timestamp":1120176000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,7]]},"abstract":"<jats:p>\n            A directed multigraph is said to be\n            <jats:italic>d<\/jats:italic>\n            -regular if the indegree and outdegree of every vertex is exactly\n            <jats:italic>d<\/jats:italic>\n            . By Hall's theorem, one can represent such a multigraph as a combination of at most\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            cycle covers, each taken with an appropriate multiplicity. We prove that if the\n            <jats:italic>d<\/jats:italic>\n            -regular multigraph does not contain more than \u230a\n            <jats:italic>d\/2<\/jats:italic>\n            \u230b copies of any 2-cycle then we can find a similar decomposition into\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>pairs of cycle covers<\/jats:italic>\n            where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair.This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2\/3 of the weight of the longest tour. This improves upon the previous 5\/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one.For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log\n            <jats:sub>2<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            . Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2\/3, previously 3\/5) and maximum asymmetric TSP with triangle inequality (factor 10\/13, previously 3\/4).\n          <\/jats:p>","DOI":"10.1145\/1082036.1082041","type":"journal-article","created":{"date-parts":[[2005,11,7]],"date-time":"2005-11-07T16:00:45Z","timestamp":1131379245000},"page":"602-626","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":96,"title":["Approximation algorithms for asymmetric TSP by decomposing directed regular multigraphs"],"prefix":"10.1145","volume":"52","author":[{"given":"Haim","family":"Kaplan","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nira","family":"Shafrir","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, New York"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2005,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00446-5"},{"key":"e_1_2_1_2_1","volume-title":"WADS '95: Proceedings of the 4th International Workshop on Algorithms and Data Structures. Springer-Verlag","author":"Armen C.","unstructured":"Armen , C. , and Stein , C . 1995. Improved length bounds for the shortest superstring problem (extended abstract) . In WADS '95: Proceedings of the 4th International Workshop on Algorithms and Data Structures. Springer-Verlag , London, UK, 494--505.]] Armen, C., and Stein, C. 1995. Improved length bounds for the shortest superstring problem (extended abstract). In WADS '95: Proceedings of the 4th International Workshop on Algorithms and Data Structures. Springer-Verlag, London, UK, 494--505.]]"},{"key":"e_1_2_1_3_1","volume-title":"CPM '96: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching. Springer-Verlag","author":"Armen C.","unstructured":"Armen , C. , and Stein , C . 1996. A 2-2\/3-approximation algorithm for the shortest superstring problem . In CPM '96: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching. Springer-Verlag , London, UK, 87--101.]] Armen, C., and Stein, C. 1996. A 2-2\/3-approximation algorithm for the shortest superstring problem. In CPM '96: Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching. Springer-Verlag, London, UK, 87--101.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Barvinok A. Gimadi E. K. and Serdyukov A. 2002. The maximum Traveling Salesman Problem. In The Traveling Salesman Problem and Its Variations G. Gutin and A. Punnen Eds. Kluwer 585--607.]]  Barvinok A. Gimadi E. K. and Serdyukov A. 2002. The maximum Traveling Salesman Problem. In The Traveling Salesman Problem and Its Variations G. Gutin and A. Punnen Eds. Kluwer 585--607.]]","DOI":"10.1007\/0-306-48213-4_12"},{"key":"e_1_2_1_5_1","volume-title":"SODA '03: Proceedings of the 14th Annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics","author":"Bl\u00e4ser M.","year":"2003","unstructured":"Bl\u00e4ser , M. 2003 . A new approximation algorithm for the asymmetric TSP with triangle inequality . In SODA '03: Proceedings of the 14th Annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics , Philadelphia, Pa., 638--645.]] Bl\u00e4ser, M. 2003. A new approximation algorithm for the asymmetric TSP with triangle inequality. In SODA '03: Proceedings of the 14th Annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, Pa., 638--645.]]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Bl\u00e4ser M. 2004. A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In APPROX-RANDOM. 61--71.]]  Bl\u00e4ser M. 2004. A 3\/4-approximation algorithm for maximum ATSP with weights zero and one. In APPROX-RANDOM. 61--71.]]","DOI":"10.1007\/978-3-540-27821-4_6"},{"key":"e_1_2_1_7_1","volume-title":"APPROX '02: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer-Verlag","author":"Bl\u00e4ser M.","unstructured":"Bl\u00e4ser , M. , and Manthey , B . 2002. Two approximation algorithms for 3-cycle covers . In APPROX '02: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer-Verlag , London, UK, 40--50.]] Bl\u00e4ser, M., and Manthey, B. 2002. Two approximation algorithms for 3-cycle covers. In APPROX '02: Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer-Verlag, London, UK, 40--50.]]"},{"key":"e_1_2_1_8_1","volume-title":"ESA '01: Proceedings of the 9th Annual European Symposium on Algorithms. Springer-Verlag","author":"Bl\u00e4ser M.","unstructured":"Bl\u00e4ser , M. , and Siebert , B . 2001. Computing cycle covers without short cycles . In ESA '01: Proceedings of the 9th Annual European Symposium on Algorithms. Springer-Verlag , London, UK, 368--379.]] Bl\u00e4ser, M., and Siebert, B. 2001. Computing cycle covers without short cycles. In ESA '01: Proceedings of the 9th Annual European Symposium on Algorithms. Springer-Verlag, London, UK, 368--379.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0861"},{"key":"e_1_2_1_11_1","volume-title":"Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. rep. 388. Graduate School of Industrial Administration","author":"Christofides N.","unstructured":"Christofides , N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. rep. 388. Graduate School of Industrial Administration , Carnegic Mellon University , Pittsburgh, PA .]] Christofides, N. 1976. Worst-case analysis of a new heuristic for the travelling salesman problem. Tech. rep. 388. Graduate School of Industrial Administration, Carnegic Mellon University, Pittsburgh, PA.]]"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0823"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-1001-6"},{"key":"e_1_2_1_14_1","volume-title":"ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag","author":"Engebretsen L.","unstructured":"Engebretsen , L. , and Karpinski , M . 2001. Approximation hardness of TSP with bounded metrics . In ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag , London, UK, 201--212.]] Engebretsen, L., and Karpinski, M. 2001. Approximation hardness of TSP with bounded metrics. In ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming. Springer-Verlag, London, UK, 201--212.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120103"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00097-1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(01)00234-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.18.6.1138"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584070"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Press, Los Alamitos, Calif., 166--177","author":"Kosaraju S.","unstructured":"Kosaraju , S. , Park , J. , and Stein , C . 1994. Long tours and short superstrings . In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Press, Los Alamitos, Calif., 166--177 .]] Kosaraju, S., Park, J., and Stein, C. 1994. Long tours and short superstrings. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Press, Los Alamitos, Calif., 166--177.]]"},{"key":"e_1_2_1_22_1","first-page":"55","article-title":"Polynomial algorithms with the estimates 3\/4 and 5\/6 for the traveling salesman problem of the maximum (Russian)","volume":"26","author":"Kostochka A. V.","year":"1985","unstructured":"Kostochka , A. V. , and Serdyukov , A. I. 1985 . Polynomial algorithms with the estimates 3\/4 and 5\/6 for the traveling salesman problem of the maximum (Russian) . Upravlyaemye Sistemy 26 , 55 -- 59 .]] Kostochka, A. V., and Serdyukov, A. I. 1985. Polynomial algorithms with the estimates 3\/4 and 5\/6 for the traveling salesman problem of the maximum (Russian). Upravlyaemye Sistemy 26, 55--59.]]","journal-title":"Upravlyaemye Sistemy"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102402861"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/2781820.2781821"},{"key":"e_1_2_1_25_1","first-page":"80","article-title":"The traveling salesman problem of the maximum (Russian)","volume":"25","author":"Serdyukov A. I.","year":"1984","unstructured":"Serdyukov , A. I. 1984 . The traveling salesman problem of the maximum (Russian) . Upravlyaemye Sistemy 25 , 80 -- 86 .]] Serdyukov, A. I. 1984. The traveling salesman problem of the maximum (Russian). Upravlyaemye Sistemy 25, 80--86.]]","journal-title":"Upravlyaemye Sistemy"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796324661"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90167-3"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794286125"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90044-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90103-3"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082041","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1082036.1082041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:18:46Z","timestamp":1750263526000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1082036.1082041"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,7]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2005,7]]}},"alternative-id":["10.1145\/1082036.1082041"],"URL":"https:\/\/doi.org\/10.1145\/1082036.1082041","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,7]]},"assertion":[{"value":"2005-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}