Practical Algorithms with Guaranteed Approximation Ratio for Traveling Tournament Problem with Maximum Tour Length 2

References

• [1] Anagnostopoulos A, Michel L, Van Hentenryck P, Vergados Y (2006) A simulated annealing approach to the traveling tournament problem. J. Scheduling 9(2):177–193.Crossref, Google Scholar
• [2] Bhattacharyya R (2016) Complexity of the unconstrained traveling tournament problem. Oper. Res. Lett. 44(5):649–654.Crossref, Google Scholar
• [3] Bulck DV, Goossens DR, Schönberger J, Guajardo M (2020) Robinx: A three-field classification and unified data format for round-robin sports timetabling. Eur. J. Oper. Res. 280(2):568–580.Crossref, Google Scholar
• [4] Campbell RT, Chen DS (1976) A minimum distance basketball scheduling problem. Machol RE, Ladany SP, eds. Management Science in Sports, vol. 4 (North-Holland, New York), 15–26.Google Scholar
• [5] Chatterjee D (2021) Complexity of traveling tournament problem with trip length more than three. Preprint, submitted October 5, https://arxiv.org/abs/2110.02300.Google Scholar
• [6] Chatterjee D, Roy BK (2021) An improved scheduling algorithm for traveling tournament problem with maximum trip length two. Müller-Hannemann M, Perea F, eds. 21st Sympos. Algorithmic Approaches Transportation Model. Optim. Systems, ATMOS 2021, OASIcs, vol. 96 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 16:1–16:15.Google Scholar
• [7] de Werra D (1988) Some models of graphs for scheduling sports competitions. Discrete Appl. Math. 21(1):47–65.Crossref, Google Scholar
• [8] Di Gaspero L, Schaerf A (2007) A composite-neighborhood tabu search approach to the traveling tournament problem. J. Heuristics 13(2):189–207.Crossref, Google Scholar
• [9] Easton K, Nemhauser GL, Trick MA (2001) The traveling tournament problem description and benchmarks. Walsh T, ed. Principles Practice Constraint Programming - CP 2001, 7th Internat. Conf., Lecture Notes in Computer Science, vol. 2239 (Springer, Berlin, Heidelberg), 580–584.Crossref, Google Scholar
• [10] Easton K, Nemhauser GL, Trick MA (2002) Solving the travelling tournament problem: A combined integer programming and constraint programming approach. Burke EK, De Causmaecker P, eds. Practice Theory Automated Timetabling IV, 4th Internat. Conf., PATAT 2002, Lecture Notes in Computer Science, vol. 2740 (Springer, Berlin, Heidelberg), 100–112.Google Scholar
• [11] Gabow HN (1974) Implementation of algorithms for maximum matching on nonbipartite graphs. PhD thesis, Stanford University, Stanford, CA.Google Scholar
• [12] Goerigk M, Hoshino R, Kawarabayashi K, Westphal S (2014) Solving the traveling tournament problem by packing three-vertex paths. Brodley CE, Stone P, eds. Proc. Twenty-Eighth (AAAI) Conf. Artificial Intelligence (AAAI Press, Palo Alto, CA), 2271–2277.Crossref, Google Scholar
• [13] Hoshino R, Kawarabayashi K (2012) Generating approximate solutions to the TTP using a linear distance relaxation. J. Artificial Intelligence Res. 45(12):257–286.Crossref, Google Scholar
• [14] Hoshino R, Kawarabayashi K-i (2013) An approximation algorithm for the bipartite traveling tournament problem. Math. Oper. Res. 38(4):720–728.Link, Google Scholar
• [15] Imahori S (2021) A 1+O(1/N) approximation algorithm for TTP(2). Preprint, submitted August 19, https://arxiv.org/abs/2108.08444.Google Scholar
• [16] Imahori S, Matsui T, Miyashiro R (2014) A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Ann. Oper. Res. 218(1):237–247.Crossref, Google Scholar
• [17] Kendall G, Knust S, Ribeiro CC, Urrutia S (2010) Scheduling in sports: An annotated bibliography. Comput. Oper. Res. 37(1):1–19.Crossref, Google Scholar
• [18] Lawler E (1976) Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York).Google Scholar
• [19] Lim A, Rodrigues B, Zhang X (2006) A simulated annealing and hill-climbing algorithm for the traveling tournament problem. Eur. J. Oper. Res. 174(3):1459–1478.Crossref, Google Scholar
• [20] Miyashiro R, Matsui T, Imahori S (2012) An approximation algorithm for the traveling tournament problem. Ann. Oper. Res. 194(1):317–324.Crossref, Google Scholar
• [21] Motwani R, Raghavan P (1995) Randomized Algorithms (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [22] Rasmussen RV, Trick MA (2008) Round robin scheduling—A survey. Eur. J. Oper. Res. 188(3):617–636.Crossref, Google Scholar
• [23] Thielen C, Westphal S (2011) Complexity of the traveling tournament problem. Theoret. Comput. Sci. 412(4):345–351.Crossref, Google Scholar
• [24] Thielen C, Westphal S (2012) Approximation algorithms for TTP(2). Math. Methods Oper. Res. 76(1):1–20.Crossref, Google Scholar
• [25] Trick M (2022) Challenge traveling tournament instances. Accessed December 31, 2022, http://mat.gsia.cmu.edu/TOURN/.Google Scholar
• [26] Westphal S, Noparlik K (2014) A 5.875-approximation for the traveling tournament problem. Ann. Oper. Res. 218(1):347–360.Crossref, Google Scholar
• [27] 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. 41st Internat. Sympos. Math. Foundations Comput. Sci. (MFCS) 2016, vol. 58 (Schloss Dagstuhl Leibniz-Zentrum für Informatik, Wadern, Germany), 89:1–89:14.Google Scholar
• [28] Yamaguchi D, Imahori S, Miyashiro R, Matsui T (2011) An improved approximation algorithm for the traveling tournament problem. Algorithmica 61(4):1077–1091.Crossref, Google Scholar
• [29] Zhao J, Xiao M (2021) A further improvement on approximating TTP-2. Chen CY, Hon WK, Hung LJ, Lee CW, eds. COCOON 27th Internat. Comput. Combinatorics Conf. 2021, Lecture Notes in Computer Science, vol. 13025 (Springer, Berlin, Heidelberg), 137–149.Google Scholar
• [30] Zhao J, Xiao M (2021) The traveling tournament problem with maximum tour length two: A practical algorithm with an improved approximation bound. Zhou ZH, ed. Proc. Thirtieth Internat. Joint Conf. Artificial Intelligence (IJCAI, California), 4206–4212.Google Scholar
• [31] Zhao J, Xiao M, Xu C (2022) Improved approximation algorithms for the traveling tournament problem. Ganian R, Silva A, eds. 47th Internat. Sympos. Math. Foundations Comput. Sci. (MFCS) 2022, LIPIcs, vol. 241 (Schloss Dagstuhl—Leibniz-Zentrum für Informatik, Wadern, Germany), 83:1–83:15.Google Scholar