caa a22 4500 445805331 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20111201xx s 000 0 eng 10.1007/s00453-011-9579-1 doi (NATIONALLICENCE)springer-10.1007/s00453-011-9579-1 An Improved Approximation Algorithm for the Traveling Tournament Problem [Elektronische Daten] [Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, Tomomi Matsui] 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 mostk. 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). Springer Science+Business Media, LLC, 2011 Traveling tournament problem nationallicence Approximation algorithm nationallicence Lower bound nationallicence Timetabling nationallicence Scheduling nationallicence Yamaguchi Daisuke Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, 112-8551, Tokyo, Japan aut Imahori Shinji Graduate School of Engineering, Nagoya University, Furo-cho, Chikusa-ku, 464-8603, Nagoya, Japan aut Miyashiro Ryuhei Institute of Engineering, Tokyo University of Agriculture and Technology, Naka-cho, Koganei, 184-8588, Tokyo, Japan aut Matsui Tomomi Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, 112-8551, Tokyo, Japan aut Algorithmica Springer-Verlag 61/4(2011-12-01), 1077-1091 0178-4617 61:4<1077 2011 61 453 https://doi.org/10.1007/s00453-011-9579-1 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-011-9579-1 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Yamaguchi Daisuke Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, 112-8551, Tokyo, Japan aut NATIONALLICENCE 700 1- Imahori Shinji Graduate School of Engineering, Nagoya University, Furo-cho, Chikusa-ku, 464-8603, Nagoya, Japan aut NATIONALLICENCE 700 1- Miyashiro Ryuhei Institute of Engineering, Tokyo University of Agriculture and Technology, Naka-cho, Koganei, 184-8588, Tokyo, Japan aut NATIONALLICENCE 700 1- Matsui Tomomi Faculty of Science and Engineering, Chuo University, Kasuga, Bunkyo-ku, 112-8551, Tokyo, Japan aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/4(2011-12-01), 1077-1091 0178-4617 61:4<1077 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer