IDEAS home Printed from https://ideas.repec.org/a/bpj/jqsprt/v12y2016i3p139-149n2.html
   My bibliography  Save this article

A combined approximation for the traveling tournament problem and the traveling umpire problem

Author

Listed:
  • Bender Marco

    (Clausthal University of Technology – Institute for Applied Stochastics and Operations Research, Germany)

  • Westphal Stephan

    (Clausthal University of Technology – Institute for Applied Stochastics and Operations Research, Germany)

Abstract

We consider the traveling tournament problem (TTP) and the traveling umpire problem (TUP). In TTP, the task is to design a double round-robin schedule, where no two teams play against each other in two consecutive rounds, and the total travel distance is minimized. In TUP, the task is to find an assignment of umpires for a given tournament such that every umpire handles at least one game at every team’s home venue and an umpire neither visits a venue nor sees a team (home or away) too often. The task is to minimize the total distance traveled by the umpires. We present a combined approximation for this problem, when the number of umpires is odd. We therefore first design an approximation algorithm for TTP and then show how to define an umpire assignment for this tournament such that a constant-factor approximation for TUP is guaranteed.

Suggested Citation

  • Bender Marco & Westphal Stephan, 2016. "A combined approximation for the traveling tournament problem and the traveling umpire problem," Journal of Quantitative Analysis in Sports, De Gruyter, vol. 12(3), pages 139-149, September.
    • Handle: RePEc:bpj:jqsprt:v:12:y:2016:i:3:p:139-149:n:2
    DOI: 10.1515/jqas-2015-0111
    as

    Download full text from publisher

    File URL: https://doi.org/10.1515/jqas-2015-0111
    Download Restriction: For access to full text, subscription to the journal or payment for the individual article is required.
    File URL: https://libkey.io/10.1515/jqas-2015-0111?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Clemens Thielen & Stephan Westphal, 2012. "Approximation algorithms for TTP(2)," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(1), pages 1-20, August.
    2. Lim, A. & Rodrigues, B. & Zhang, X., 2006. "A simulated annealing and hill-climbing algorithm for the traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 174(3), pages 1459-1478, November.
    3. Wauters, Tony & Van Malderen, Sam & Vanden Berghe, Greet, 2014. "Decomposition and local search based methods for the traveling umpire problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 886-898.
    4. Trick, Michael A. & Yildiz, Hakan, 2012. "Locally Optimized Crossover for the Traveling Umpire Problem," European Journal of Operational Research, Elsevier, vol. 216(2), pages 286-292.
    5. de Oliveira, Lucas & de Souza, Cid C. & Yunes, Tallys, 2014. "Improved bounds for the traveling umpire problem: A stronger formulation and a relax-and-fix heuristic," European Journal of Operational Research, Elsevier, vol. 236(2), pages 592-600.
    6. Ryuhei Miyashiro & Tomomi Matsui & Shinji Imahori, 2012. "An approximation algorithm for the traveling tournament problem," Annals of Operations Research, Springer, vol. 194(1), pages 317-324, April.
    7. Ribeiro, Celso C. & Urrutia, Sebastian, 2007. "Heuristics for the mirrored traveling tournament problem," European Journal of Operational Research, Elsevier, vol. 179(3), pages 775-787, June.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Guillermo Durán & Mario Guajardo & Facundo Gutiérrez, 2022. "Efficient referee assignment in Argentinean professional basketball leagues using operations research methods," Annals of Operations Research, Springer, vol. 316(2), pages 1121-1139, September.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Toffolo, Túlio A.M. & Wauters, Tony & Van Malderen, Sam & Vanden Berghe, Greet, 2016. "Branch-and-bound with decomposition-based lower bounds for the Traveling Umpire Problem," European Journal of Operational Research, Elsevier, vol. 250(3), pages 737-744.
    2. Xue, Li & Luo, Zhixing & Lim, Andrew, 2015. "Two exact algorithms for the traveling umpire problem," European Journal of Operational Research, Elsevier, vol. 243(3), pages 932-943.
    3. Guillermo Durán, 2021. "Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 125-155, April.
    4. Wauters, Tony & Van Malderen, Sam & Vanden Berghe, Greet, 2014. "Decomposition and local search based methods for the traveling umpire problem," European Journal of Operational Research, Elsevier, vol. 238(3), pages 886-898.
    5. M B Wright, 2009. "50 years of OR in sport," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 161-168, May.
    6. Brigitte Werners & Thomas Wülfing, 2007. "Optimierung von Spielplänen am Beispiel der Fußball-Bundesliga-Saison 2006/07," Metrika: International Journal for Theoretical and Applied Statistics, Springer, vol. 18(2), pages 207-221, August.
    7. Özlü, Oğuzhan & Sokol, Joel, 2016. "An optimization approach to designing a baseball scout network," European Journal of Operational Research, Elsevier, vol. 255(3), pages 948-960.
    8. Yun-Chia Liang & Yen-Yu Lin & Angela Hsiang-Ling Chen & Wei-Sheng Chen, 2021. "Variable Neighborhood Search for Major League Baseball Scheduling Problem," Sustainability, MDPI, vol. 13(7), pages 1-18, April.
    9. Richard Hoshino & Ken-ichi Kawarabayashi, 2013. "An Approximation Algorithm for the Bipartite Traveling Tournament Problem," Mathematics of Operations Research, INFORMS, vol. 38(4), pages 720-728, November.
    10. Marc Goerigk & Stephan Westphal, 2016. "A combined local search and integer programming approach to the traveling tournament problem," Annals of Operations Research, Springer, vol. 239(1), pages 343-354, April.
    11. Stephan Westphal & Karl Noparlik, 2014. "A 5.875-approximation for the Traveling Tournament Problem," Annals of Operations Research, Springer, vol. 218(1), pages 347-360, July.
    12. Rasmussen, Rasmus V. & Trick, Michael A., 2008. "Round robin scheduling - a survey," European Journal of Operational Research, Elsevier, vol. 188(3), pages 617-636, August.
    13. David Van Bulck & Dries Goossens & Jo¨rn Scho¨nberger & Mario Guajardo, 2020. "An Instance Data Repository for the Round-robin Sports Timetabling Problem," Management and Labour Studies, XLRI Jamshedpur, School of Business Management & Human Resources, vol. 45(2), pages 184-200, May.
    14. Hoshino, Richard & Kawarabayashi, Ken-ichi, 2011. "A multi-round generalization of the traveling tournament problem and its application to Japanese baseball," European Journal of Operational Research, Elsevier, vol. 215(2), pages 481-497, December.
    15. Young Dae Ko & Seung Hwan Jung & Sung Hee Kim & Sung Wook Lee, 2018. "Sustainable Sport Scheduling Approach Considering Team Equity for the Korean Professional Baseball League," Sustainability, MDPI, vol. 10(2), pages 1-11, February.
    16. Alireza Tajbakhsh & Kourosh Eshghi & Azam Shamsi, 2012. "A hybrid PSO-SA algorithm for the travelling tournament problem," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 6(1), pages 2-25.
    17. Kadri Sylejmani & Edon Gashi & Adrian Ymeri, 2023. "Simulated annealing with penalization for university course timetabling," Journal of Scheduling, Springer, vol. 26(5), pages 497-517, October.
    18. Mancini Simona & Isabello Andrea, 2014. "Fair referee assignment for the Italian soccer serieA," Journal of Quantitative Analysis in Sports, De Gruyter, vol. 10(2), pages 153-160, June.
    19. Nicolau, Juan L., 2011. "The decision to raise firm value through a sports-business exchange: How much are Real Madrid's goals worth to its president's company's goals?," European Journal of Operational Research, Elsevier, vol. 215(1), pages 281-288, November.
    20. Clemens Thielen & Stephan Westphal, 2012. "Approximation algorithms for TTP(2)," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 76(1), pages 1-20, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:bpj:jqsprt:v:12:y:2016:i:3:p:139-149:n:2. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Peter Golla (email available below). General contact details of provider: https://www.degruyter.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.