{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T09:10:22Z","timestamp":1778231422959,"version":"3.51.4"},"reference-count":38,"publisher":"Institute for Operations Research and the Management Sciences (INFORMS)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematics of OR"],"published-print":{"date-parts":[[2026,5]]},"abstract":"<jats:p>The bipartite traveling tournament problem (BTTP) addresses interleague sports scheduling, which aims to design a feasible bipartite tournament between two n-team leagues under some constraints such that the total traveling distance of all participating teams is minimized. Since its introduction, several methods have been developed to design feasible schedules for the National Basketball Association (NBA), Nippon Professional Baseball (NPB), and so on. In terms of solution quality with a theoretical guarantee, previously, only a [Formula: see text]-approximation is known for the case that [Formula: see text]. Whether there are similar results for the cases that [Formula: see text] and [Formula: see text] was asked in the literature. In this paper, we answer this question positively by proposing a [Formula: see text]-approximation algorithm for any n and any constant [Formula: see text], which also improves the previous approximation ratio for the case that [Formula: see text].<\/jats:p>\n                  <jats:p>Funding: This research was supported by the National Natural Science Foundation of China [Grants 62372095, 62172077, and 62350710215].<\/jats:p>","DOI":"10.1287\/moor.2024.0518","type":"journal-article","created":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T10:54:54Z","timestamp":1746183294000},"page":"988-1006","source":"Crossref","is-referenced-by-count":0,"title":["An Improved Algorithm for a Bipartite Traveling Tournament in Interleague Sports Scheduling"],"prefix":"10.1287","volume":"51","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2322-750X","authenticated-orcid":false,"given":"Jingyang","family":"Zhao","sequence":"first","affiliation":[{"name":"University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[{"name":"University of Electronic Science and Technology of China, Chengdu, Sichuan 611731, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"109","reference":[{"key":"B1","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-006-7187-8"},{"key":"B2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.07.023"},{"key":"B3","unstructured":"Chatterjee D, Roy BK (2021) An improved scheduling algorithm for traveling tournament problem with maximum trip length two. M\u00fcller-Hannemann M, Perea F, eds.\n                      21st Sympos. Algorithmic Approaches Transportation Modelling Optimization Systems (ATMOS 2021)\n                      , vol. 96 (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 16:1\u201316:15."},{"key":"B4","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"B5","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-006-9007-x"},{"issue":"1","key":"B6","first-page":"125","volume":"29","author":"Dur\u00e1n G","year":"2021","journal-title":"Trans. Oper. Res."},{"key":"B7","doi-asserted-by":"crossref","unstructured":"Easton K, Nemhauser G, Trick M (2001) The traveling tournament problem: Description and benchmarks. Walsh T, eds.\n                      Principles Practice Constraint Programming. CP 2001\n                      , Lecture Notes in Computer Science, vol. 2239 (Springer, Berlin, Heidelberg), 580\u2013584.","DOI":"10.1007\/3-540-45578-7_43"},{"key":"B8","doi-asserted-by":"crossref","unstructured":"Easton K, Nemhauser GL, Trick MA (2002) Solving the travelling tournament problem: A combined integer programming and constraint programming approach. Burke E, De Causmaecker P, eds.\n                      Practice Theory Automated Timetabling IV.\n                      PATAT 2002, Lecture Notes in Computer Science, vol. 2740 (Springer, Berlin, Heidelberg), 100\u2013109.","DOI":"10.1007\/978-3-540-45157-0_6"},{"key":"B9","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00319"},{"key":"B10","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-014-1586-6"},{"key":"B11","doi-asserted-by":"crossref","unstructured":"Goerigk M, Hoshino R, Ki K, Westphal S (2014) Solving the traveling tournament problem by packing three-vertex paths.\n                      AAAI\u201914: Proc. 28th AAAI Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 2271\u20132277.","DOI":"10.1609\/aaai.v28i1.9031"},{"key":"B12","unstructured":"Hartvigsen D (1984) Extensions of matching theory. Unpublished PhD thesis, Carnegie-Mellon University, Pittsburgh."},{"key":"B13","unstructured":"Hentenryck PV, Vergados Y (2007) Population-based simulated annealing for traveling tournaments.\n                      AAAI\u201907: Proc. 22nd Natl. Conf. Artificial Intelligence\n                      , vol. 1 (AAAI Press, Washington, DC), 267\u2013272."},{"issue":"1","key":"B14","first-page":"91","volume":"42","author":"Hoshino R","year":"2011","journal-title":"J. Artificial Intelligence Res."},{"key":"B15","unstructured":"Hoshino R, Kawarabayashi K (2011b) The distance-optimal inter-league schedule for Japanese pro baseball. Salido MA, Bart\u00e1k R, Policella N, eds.\n                      Proc. ICAPS 2011 Workshop Constraint Satisfaction Techniques Planning Scheduling Problems (COPLAS)\n                      (AAAI Press, Washington, DC), 71\u201378."},{"key":"B16","doi-asserted-by":"crossref","unstructured":"Hoshino R, Kawarabayashi K (2011c) The inter-league extension of the traveling tournament problem and its application to sports scheduling.\n                      AAAI\u201911: Proc. 25th AAAI Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 977\u2013984.","DOI":"10.1609\/aaai.v25i1.8003"},{"key":"B17","doi-asserted-by":"crossref","unstructured":"Hoshino R, Kawarabayashi K (2012) The linear distance traveling tournament problem.\n                      AAAI\u201912: Proc. 26th AAAI Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 1770\u20131778.","DOI":"10.1609\/aaai.v26i1.8358"},{"key":"B18","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2013.0597"},{"key":"B19","unstructured":"Imahori S (2021) A 1+O(1\/N) approximation algorithm for TTP(2). Preprint, submitted August 19, https:\/\/arxiv.org\/abs\/2108.08444."},{"key":"B20","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2009.05.013"},{"key":"B21","volume-title":"The Art of Computer Programming","volume":"3","author":"Knuth DE","year":"1997"},{"key":"B22","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.02.065"},{"key":"B23","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-010-0742-x"},{"issue":"2","key":"B24","first-page":"158","volume":"68","author":"Sinnott RW","year":"1984","journal-title":"Sky Telescope"},{"key":"B25","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.001"},{"key":"B26","doi-asserted-by":"publisher","DOI":"10.1007\/s00186-012-0387-4"},{"key":"B27","unstructured":"Trick M (2022) Challenge traveling tournament instances. Accessed December 31, 2022, https:\/\/mat.tepper.cmu.edu\/TOURN\/."},{"key":"B28","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1061-1"},{"key":"B29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735"},{"key":"B30","unstructured":"Xiao M, Kou S (2016) An improved approximation algorithm for the traveling tournament problem with maximum trip length two. Faliszewski P, Muscholl A, Niedermeier R, eds.\n                      41st Internat. Sympos. Math. Foundations Comput. Sci. (MFCS 2016)\n                      , Leibniz International Proceedings in Informatics, vol. 58 (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 89:1\u201389:14."},{"key":"B31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9579-1"},{"key":"B32","doi-asserted-by":"crossref","unstructured":"Zhao J, Xiao M (2021a) A further improvement on approximating TTP-2. Chen CY, Hon WK, Hung LJ, Lee CW, eds.\n                      Comput. Combinatorics. COCOON 2021\n                      , Lecture Notes in Computer Science, vol. 13025 (Springer, Cham, Switzerland), 137\u2013149.","DOI":"10.1007\/978-3-030-89543-3_12"},{"key":"B33","doi-asserted-by":"crossref","unstructured":"Zhao J, Xiao M (2021b) The traveling tournament problem with maximum tour length two: A practical algorithm with an improved approximation bound.\n                      Proc. 30th Internat. Joint Conf. Artificial Intelligence (IJCAI 2021)\n                      (IJCAI Organization, California), 4206\u20134212.","DOI":"10.24963\/ijcai.2021\/578"},{"key":"B34","doi-asserted-by":"crossref","unstructured":"Zhao J, Xiao M (2023) The linear distance traveling tournament problem allows an EPTAS.\n                      AAAI\u201923: Proc. 37th AAAI Conf. Artificial Intelligence\n                      (AAAI Press, Washington, DC), 12155\u201312162.","DOI":"10.1609\/aaai.v37i10.26433"},{"key":"B35","unstructured":"Zhao J, Xiao M (2024a) A better approximation for bipartite traveling tournament in inter-league sports scheduling.\n                      IJCAI \u201824: Proc. 33rd Internat. Joint Conf. Artificial Intelligence\n                      (IJCAI Organization, California), 6814\u20136822."},{"key":"B36","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2022.0356"},{"key":"B37","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-025-06483-1"},{"key":"B38","unstructured":"Zhao J, Xiao M, Xu C (2022) Improved approximation algorithms for the traveling tournament problem. Szeider S, Ganian R, Silva A, eds.\n                      47th Internat. Sympos. Math. Foundations Comput. Sci. (MFCS 2022)\n                      , Leibniz International Proceedings in Informatics, vol. 241 (Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Wadern, Germany), 83:1\u201383:15."}],"container-title":["Mathematics of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/pubsonline.informs.org\/doi\/pdf\/10.1287\/moor.2024.0518","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T08:23:24Z","timestamp":1778228604000},"score":1,"resource":{"primary":{"URL":"https:\/\/pubsonline.informs.org\/doi\/10.1287\/moor.2024.0518"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,5]]}},"alternative-id":["10.1287\/moor.2024.0518"],"URL":"https:\/\/doi.org\/10.1287\/moor.2024.0518","relation":{},"ISSN":["0364-765X","1526-5471"],"issn-type":[{"value":"0364-765X","type":"print"},{"value":"1526-5471","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5]]}}}