{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T04:11:18Z","timestamp":1769919078989,"version":"3.49.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T00:00:00Z","timestamp":1737417600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972070"],"award-info":[{"award-number":["61972070"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s10479-025-06483-1","type":"journal-article","created":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T11:08:35Z","timestamp":1737457715000},"page":"2287-2305","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A 5-approximation algorithm for the traveling tournament problem"],"prefix":"10.1007","volume":"346","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2322-750X","authenticated-orcid":false,"given":"Jingyang","family":"Zhao","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1012-2373","authenticated-orcid":false,"given":"Mingyu","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,21]]},"reference":[{"issue":"2","key":"6483_CR1","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/s10951-006-7187-8","volume":"9","author":"A Anagnostopoulos","year":"2006","unstructured":"Anagnostopoulos, A., Michel, L., Van Hentenryck, P., & Vergados, Y. (2006). A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9(2), 177\u2013193.","journal-title":"Journal of Scheduling"},{"issue":"4","key":"6483_CR2","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.orl.2023.06.006","volume":"51","author":"S Bendayan","year":"2023","unstructured":"Bendayan, S., Cheriyan, J., & Cheung, K. K. H. (2023). Unconstrained traveling tournament problem is APX-complete. Operations Research Letters, 51(4), 456\u2013460.","journal-title":"Operations Research Letters"},{"issue":"5","key":"6483_CR3","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1016\/j.orl.2016.07.011","volume":"44","author":"R Bhattacharyya","year":"2016","unstructured":"Bhattacharyya, R. (2016). Complexity of the unconstrained traveling tournament problem. Operations Research Letters, 44(5), 649\u2013654.","journal-title":"Operations Research Letters"},{"issue":"2","key":"6483_CR4","doi-asserted-by":"publisher","first-page":"568","DOI":"10.1016\/j.ejor.2019.07.023","volume":"280","author":"DV Bulck","year":"2020","unstructured":"Bulck, D. V., Goossens, D. R., Sch\u00f6nberger, J., & Guajardo, M. (2020). Robinx: A three-field classification and unified data format for round-robin sports timetabling. European Journal of Operational Research, 280(2), 568\u2013580.","journal-title":"European Journal of Operational Research"},{"key":"6483_CR5","unstructured":"Chatterjee, D. (2021). Complexity of traveling tournament problem with trip length more than three. CoRR abs\/2110.02300"},{"key":"6483_CR6","unstructured":"Chatterjee, D., & Roy, B.K. (2021) An improved scheduling algorithm for traveling tournament problem with maximum trip length two. In: ATMOS 2021, vol. 96, pp. 16\u201311615"},{"key":"6483_CR7","unstructured":"Christofides, N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group"},{"issue":"1","key":"6483_CR8","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0166-218X(88)90033-9","volume":"21","author":"D de Werra","year":"1988","unstructured":"de Werra, D. (1988). Some models of graphs for scheduling sports competitions. Discrete Applied Mathematics, 21(1), 47\u201365.","journal-title":"Discrete Applied Mathematics"},{"issue":"2","key":"6483_CR9","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/s10732-006-9007-x","volume":"13","author":"L Di Gaspero","year":"2007","unstructured":"Di Gaspero, L., & Schaerf, A. (2007). A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics, 13(2), 189\u2013207.","journal-title":"Journal of Heuristics"},{"issue":"1","key":"6483_CR10","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s11750-020-00576-9","volume":"29","author":"G Dur\u00e1n","year":"2021","unstructured":"Dur\u00e1n, G. (2021). Sports scheduling and other topics in sports analytics: A survey with special reference to Latin America. TOP, 29(1), 125\u2013155.","journal-title":"TOP"},{"key":"6483_CR11","doi-asserted-by":"crossref","unstructured":"Easton, K., Nemhauser, G.L. & Trick, M.A. (2002) Solving the travelling tournament problem: A combined integer programming and constraint programming approach. In: PATAT 2002. Lecture Notes in Computer Science, vol. 2740, pp. 100\u2013112","DOI":"10.1007\/978-3-540-45157-0_6"},{"key":"6483_CR12","doi-asserted-by":"crossref","unstructured":"Easton, K., Nemhauser, G., & Trick, M. (2001). The traveling tournament problem: Description and benchmarks. In: CP 2001, pp. 580\u2013584","DOI":"10.1007\/3-540-45578-7_43"},{"key":"6483_CR13","doi-asserted-by":"crossref","unstructured":"Goerigk, M., Hoshino, R., Kawarabayashi, K., & Westphal, S. (2014). Solving the traveling tournament problem by packing three-vertex paths. In: AAAI 2014, pp. 2271\u20132277","DOI":"10.1609\/aaai.v28i1.9031"},{"issue":"1","key":"6483_CR14","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1007\/s10479-014-1586-6","volume":"239","author":"M Goerigk","year":"2016","unstructured":"Goerigk, M., & Westphal, S. (2016). A combined local search and integer programming approach to the traveling tournament problem. Annals of Operations Research, 239(1), 343\u2013354.","journal-title":"Annals of Operations Research"},{"key":"6483_CR15","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1613\/jair.3713","volume":"45","author":"R Hoshino","year":"2012","unstructured":"Hoshino, R., & Kawarabayashi, K. (2012). Generating approximate solutions to the TTP using a linear distance relaxation. Journal of Artificial Intelligence Research, 45, 257\u2013286.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"4","key":"6483_CR16","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1287\/moor.2013.0597","volume":"38","author":"R Hoshino","year":"2013","unstructured":"Hoshino, R., & Kawarabayashi, K. (2013). An approximation algorithm for the bipartite traveling tournament problem. Mathematics of Operations Research, 38(4), 720\u2013728.","journal-title":"Mathematics of Operations Research"},{"key":"6483_CR17","unstructured":"Imahori, S. (2021) A 1+O(1\/N) approximation algorithm for TTP(2). CoRR abs\/2108.08444"},{"issue":"1","key":"6483_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s10479-012-1161-y","volume":"218","author":"S Imahori","year":"2014","unstructured":"Imahori, S., Matsui, T., & Miyashiro, R. (2014). A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Annals of Operations Research, 218(1), 237\u2013247.","journal-title":"Annals of Operations Research"},{"key":"6483_CR19","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Klein, N., & Gharan, S.O. (2021) A (slightly) improved approximation algorithm for metric TSP. In: STOC 2021, pp. 32\u201345","DOI":"10.1145\/3406325.3451009"},{"issue":"1","key":"6483_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.cor.2009.05.013","volume":"37","author":"G Kendall","year":"2010","unstructured":"Kendall, G., Knust, S., Ribeiro, C. C., & Urrutia, S. (2010). Scheduling in sports: An annotated bibliography. Computers & Operations Research, 37(1), 1\u201319.","journal-title":"Computers & Operations Research"},{"issue":"3","key":"6483_CR21","doi-asserted-by":"publisher","first-page":"1459","DOI":"10.1016\/j.ejor.2005.02.065","volume":"174","author":"A Lim","year":"2006","unstructured":"Lim, A., Rodrigues, B., & Zhang, X. (2006). A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174(3), 1459\u20131478.","journal-title":"European Journal of Operational Research"},{"issue":"1","key":"6483_CR22","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/s10479-010-0742-x","volume":"194","author":"R Miyashiro","year":"2012","unstructured":"Miyashiro, R., Matsui, T., & Imahori, S. (2012). An approximation algorithm for the traveling tournament problem. Annals of Operations Research, 194(1), 317\u2013324.","journal-title":"Annals of Operations Research"},{"key":"6483_CR23","first-page":"76","volume":"17","author":"AI Serdyukov","year":"1978","unstructured":"Serdyukov, A. I. (1978). Some extremal bypasses in graphs. Upravlyaemye Sistemy, 17, 76\u201379.","journal-title":"Upravlyaemye Sistemy"},{"issue":"4","key":"6483_CR24","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/j.tcs.2010.10.001","volume":"412","author":"C Thielen","year":"2011","unstructured":"Thielen, C., & Westphal, S. (2011). Complexity of the traveling tournament problem. Theoretical Computer Science, 412(4), 345\u2013351.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"6483_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00186-012-0387-4","volume":"76","author":"C Thielen","year":"2012","unstructured":"Thielen, C., & Westphal, S. (2012). Approximation algorithms for TTP(2). Mathematical Methods of Operations Research, 76(1), 1\u201320.","journal-title":"Mathematical Methods of Operations Research"},{"key":"6483_CR26","unstructured":"Trick, M. (2022) Challenge traveling tournament instances. Accessed: 2022-04-01. https:\/\/mat.tepper.cmu.edu\/TOURN\/"},{"issue":"1","key":"6483_CR27","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10479-012-1061-1","volume":"218","author":"S Westphal","year":"2014","unstructured":"Westphal, S., & Noparlik, K. (2014). A 5.875-approximation for the traveling tournament problem. Annals of Operations Research, 218(1), 347\u2013360.","journal-title":"Annals of Operations Research"},{"key":"6483_CR28","unstructured":"Xiao, M., & Kou, S. (2016). An improved approximation algorithm for the traveling tournament problem with maximum trip length two. In: MFCS 2016, vol. 58, pp. 89\u201318914"},{"issue":"4","key":"6483_CR29","doi-asserted-by":"publisher","first-page":"1077","DOI":"10.1007\/s00453-011-9579-1","volume":"61","author":"D Yamaguchi","year":"2011","unstructured":"Yamaguchi, D., Imahori, S., Miyashiro, R., & Matsui, T. (2011). An improved approximation algorithm for the traveling tournament problem. Algorithmica, 61(4), 1077\u20131091.","journal-title":"Algorithmica"},{"key":"6483_CR30","doi-asserted-by":"crossref","unstructured":"Zhao, J., & Xiao, M. (2021). A further improvement on approximating TTP-2. In: COCOON 2021. Lecture notes in computer science, vol. 13025, pp. 137\u2013149","DOI":"10.1007\/978-3-030-89543-3_12"},{"key":"6483_CR31","doi-asserted-by":"crossref","unstructured":"Zhao, J., & Xiao, M. (2021). The traveling tournament problem with maximum tour length two: A practical algorithm with an improved approximation bound. In: IJCAI 2021, pp. 4206\u20134212","DOI":"10.24963\/ijcai.2021\/578"},{"key":"6483_CR32","unstructured":"Zhao, J., & Xiao, M. (2023). The APX-hardness of the traveling tournament problem. CoRR abs\/2308.14124"},{"key":"6483_CR33","doi-asserted-by":"crossref","unstructured":"Zhao, J., & Xiao, M. (2024) Practical algorithms with guaranteed approximation ratio for traveling tournament problem with maximum tour length 2. Mathematics of Operations Research","DOI":"10.1287\/moor.2022.0356"},{"key":"6483_CR34","unstructured":"Zhao, J., Xiao, M., & Xu, C. (2022) Improved approximation algorithms for the traveling tournament problem. In: MFCS 2022,. LIPIcs, vol. 241, pp. 83\u201318315"}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06483-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-025-06483-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-025-06483-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,29]],"date-time":"2025-03-29T01:49:51Z","timestamp":1743212991000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-025-06483-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,21]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["6483"],"URL":"https:\/\/doi.org\/10.1007\/s10479-025-06483-1","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,21]]},"assertion":[{"value":"11 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}