Solving the Traveling Tournament Problem by Packing Three-Vertex Paths
Authors: Marc Goerigk, Richard Hoshino, Ken-ichi Kawarabayashi, Stephan Westphal
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We apply this three-step approach to the n-team Galaxy instances, a data set where the teams represent exoplanets located in three-dimensional space. Our method finds bestknown solutions to the Galaxy instances for four cases, n {22, 28, 34, 40}. We also explain how this algorithm can be combined to generate a new solution for the NFL28 data set, beating the previously best-known upper bound (Trick 2013) that was published in 2007. |
| Researcher Affiliation | Academia | Marc Goerigk University of Kaiserslautern Kaiserslautern, Germany Richard Hoshino Quest University Canada Squamish, British Columbia Ken-ichi Kawarabayashi National Institute of Informatics JST ERATO Kawarabayashi Large Graph Project, Tokyo, Japan Stephan Westphal University of G ottingen G ottingen, Germany |
| Pseudocode | Yes | Table 6: Expanding one time slot in U to six time slots in Zn. Table 7: The six time slot expansion for 1 k m. Table 8: The six time slot expansion for m + 1 k 2m 1. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code or links to a code repository. |
| Open Datasets | Yes | There is an online set of benchmark n-team TTP data sets (Trick 2013) with the list of best-known upper and lower bounds. |
| Dataset Splits | No | The paper does not explicitly provide training/validation/test dataset splits. It mentions 'n-team TTP data sets' and 'Galaxy instances' but without specific split information. |
| Hardware Specification | Yes | Our algorithm is coded using Maplesoft, on a stand-alone laptop with 2.75 GB main memory and a single 2.10 GHz processor. |
| Software Dependencies | Yes | Our algorithm is coded using Maplesoft, on a stand-alone laptop with 2.75 GB main memory and a single 2.10 GHz processor. |
| Experiment Setup | Yes | In Phase 2, we follow the following four-step sequence: (a) For each team (vertex) in {t1, t2, . . . , tn}, use any polynomial-time algorithm to compute a (near)-optimal P3-packing of G tk, with total weight X k. Select the P3packing with total weight X := min(X 1, X 2, . . . , X n), and reorder the n teams accordingly. This creates perm, a specific permutation of the n teams. (b) Calculate dist, the total travel distance of this schedule. (c) There are n 2 possible choices for the pair (i, j), with 1 i < j n. List these choices in some random order. Starting with the first pair, calculate the total travel distance of the schedule where teams ti and tj are swapped. As soon as we find a pair (i, j) for which the resulting schedule has total distance less than dist, swap the ith and jth entries of perm and go back to step (b). (d) End when none of the n 2 pairs (i, j) yield a schedule whose total distance is less than dist. |