{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,8,4]],"date-time":"2022-08-04T12:31:35Z","timestamp":1659616295725},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,7]]},"abstract":"\n A directed multigraph is said to be\n d<\/jats:italic>\n -regular if the indegree and outdegree of every vertex is exactly\n d<\/jats:italic>\n . By Hall's theorem, one can represent such a multigraph as a combination of at most\n n<\/jats:italic>\n 2<\/jats:sup>\n cycle covers, each taken with an appropriate multiplicity. We prove that if the\n d<\/jats:italic>\n -regular multigraph does not contain more than \u230a\n d\/2<\/jats:italic>\n \u230b copies of any 2-cycle then we can find a similar decomposition into\n n<\/jats:italic>\n 2<\/jats:sup>\n 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 2<\/jats:sub>\n n<\/jats:italic>\n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log\n 2<\/jats:sub>\n 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","source":"Crossref","is-referenced-by-count":90,"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"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Ramat-Gan, Israel"}]},{"given":"Nira","family":"Shafrir","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}]},{"given":"Maxim","family":"Sviridenko","sequence":"additional","affiliation":[{"name":"IBM T.J. Watson Research Center, Yorktown Heights, New York"}]}],"member":"320","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."},{"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."},{"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"},{"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."},{"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."},{"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","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."},{"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."},{"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","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","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\/pdf\/10.1145\/1082036.1082041","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,20]],"date-time":"2021-02-20T11:57:42Z","timestamp":1613822262000},"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":"http:\/\/dx.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":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2005,7]]}}}