An Improved Approximation Algorithm for the Traveling Tournament Problem

This paper describes the traveling tournament problem, a well-known benchmark problem in the field of tournament timetabling. We propose an approximation algorithm for the traveling tournament problem with the constraints such that both the number of consecutive away games and that of consecutive home games are at most k. When k ≤ 5, the approximation ratio of the proposed algorithm is bounded by (2k − 1)/k + O(k/n) where n denotes the number of teams; when k > 5, the ratio is bounded by (5k − 7)/(2k) + O(k/n). For k = 3, the most investigated case of the traveling tournament problem to date, the approximation ratio of the proposed algorithm is 5/3 + O(1/n); this is better than the previous approximation algorithm proposed for k = 3, whose approximation ratio is 2 + O(1/n).

Authors and Affiliations

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

   Daisuke Yamaguchi & Tomomi Matsui

2. Graduate School of Information Science and Technology, The University of Tokyo, Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan

   Shinji Imahori

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

   Ryuhei Miyashiro

Editors and Affiliations

1. Dept. of Electrical and Computer Engineering, University of Hawaii, Holmes Hall 483, 2540 Dole Street, 96822, Honolulu, HI, USA

   Yingfei Dong

2. Department of Computer Science, University of Texas at Dallas, 75083, Dallas, TX, USA

   Ding-Zhu Du

3. Department of Computer Science, University of California, 93106, Santa Barbara, CA, USA

   Oscar Ibarra

Reprints and permissions

© 2009 Springer-Verlag Berlin Heidelberg

Policies and ethics