Skip to main content
SpringerLink
Log in

A 2.75-approximation algorithm for the unconstrained traveling tournament problem

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

A 2.75-approximation algorithm is proposed for the unconstrained traveling tournament problem, which is a variant of the traveling tournament problem. For the unconstrained traveling tournament problem, this is the first proposal of an approximation algorithm with a constant approximation ratio. In addition, the proposed algorithm yields a solution that meets both the no-repeater and mirrored constraints. Computational experiments show that the algorithm generates solutions of good quality.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Westphal and Noparlik’s paper (Westphal and Noparlik 2010) and the conference version of the present paper (Imahori et al. 2010) appeared in the same conference (PATAT, 2010).

References

  • Bhattacharyya, R. (2009). A note on complexity of traveling tournament problem. Available from Optimization Online, Web page. http://www.optimization-online.org/.

  • Christofides, N. (1976). Worst-case analysis of a new heuristic for the traveling salesman problem (Report 388). Graduate School of Industrial Administration, Carnegie-Mellon University.

  • Cook, W. (2011). Concorde TSP solver. Web page, as of http://www.tsp.gatech.edu/concorde.html.

  • Easton, K., Nemhauser, G., & Trick, M. (2001). The traveling tournament problem: description and benchmarks. In Lecture notes in computer science (Vol. 2239, pp. 580–584).

    Google Scholar 

  • Fujiwara, N., Imahori, S., Matsui, T., & Miyashiro, R. (2007). Constructive algorithms for the constant distance traveling tournament problem. In Lecture notes in computer science (Vol. 3867, pp. 135–146).

    Google Scholar 

  • Gurobi Optimization (2011). Gurobi Optimizer 4.5.1. http://www.gurobi.com/.

  • Imahori, S., Matsui, T., & Miyashiro, R. (2010). An approximation algorithm for the unconstrained traveling tournament problem. In Proceedings of the 8th international conference on the practice and theory of automated timetabling (PATAT) (pp. 508–512).

    Google Scholar 

  • Kendall, G., Knust, S., Ribeiro, C. C., & Urrutia, S. (2010). Scheduling in sports: an annotated bibliography. Computers and Operations Research, 37, 1–19.

    Article  Google Scholar 

  • Miyashiro, R., Matsui, T., & Imahori, S. (2012). An approximation algorithm for the traveling tournament problem. Annals of Operations Research, 194, 317–324.

    Article  Google Scholar 

  • Rasmussen, R. V., & Trick, M. A. (2008). Round robin scheduling—a survey. European Journal of Operational Research, 188, 617–636.

    Article  Google Scholar 

  • Thielen, C., & Westphal, S. (2010). Approximating the traveling tournament problem with maximum tour length 2. In Lecture notes in computer science (Vol. 6507, pp. 303–314).

    Google Scholar 

  • Thielen, C., & Westphal, S. (2011). Complexity of the traveling tournament problem. Theoretical Computer Science, 412, 345–351.

    Article  Google Scholar 

  • Trick, M. (2010). Challenge traveling tournament problems. Web page, as of http://mat.gsia.cmu.edu/TOURN/.

  • Trick, M. A. (2011). Sports scheduling. In Springer optimization and its applications: Vol. 45. Hybrid optimization (pp. 489–508).

    Chapter  Google Scholar 

  • Urrutia, S., & Ribeiro, C. C. (2006). Maximizing breaks and bounding solutions to the mirrored traveling tournament problem. Discrete Applied Mathematics, 154, 1932–1938.

    Article  Google Scholar 

  • Westphal, S., & Noparlik, K. (2010). A 5.875-approximation for the traveling tournament problem. In Proceedings of the 8th international conference on the practice and theory of automated timetabling (PATAT) (pp. 417–426).

    Google Scholar 

  • Yamaguchi, D., Imahori, S., Miyashiro, R., & Matsui, T. (2011). An improved approximation algorithm for the traveling tournament problem. Algorithmica, 61, 1077–1091.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Engineering, Nagoya University, Furo-cho, Chikusa-ku, Nagoya, 464-8603, Japan

    Shinji Imahori

  2. Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, Tokyo, 112-8551, Japan

    Tomomi Matsui

  3. Institute of Engineering, Tokyo University of Agriculture and Technology, Naka-cho, Koganei, Tokyo, 184-8588, Japan

    Ryuhei Miyashiro

Authors
  1. Shinji Imahori
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tomomi Matsui
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ryuhei Miyashiro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tomomi Matsui.

Additional information

The present study was supported in part by Grants-in-Aid for Scientific Research, by the Ministry of Education, Culture, Sports, Science and Technology of Japan.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Imahori, S., Matsui, T. & Miyashiro, R. A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Ann Oper Res 218, 237–247 (2014). https://doi.org/10.1007/s10479-012-1161-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-012-1161-y

Keywords

Search

Navigation