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

Bender Marco () and Westphal Stephan
Additional contact information
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

Journal of Quantitative Analysis in Sports, 2016, vol. 12, issue 3, 139-149

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.

Keywords: approximation algorithms; sports scheduling; traveling tournament problem; traveling umpire problem (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1515/jqas-2015-0111 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:jqsprt:v:12:y:2016:i:3:p:139-149:n:2

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/jqas/html

DOI: 10.1515/jqas-2015-0111

Access Statistics for this article

Journal of Quantitative Analysis in Sports is currently edited by Mark Glickman

More articles in Journal of Quantitative Analysis in Sports from De Gruyter
Bibliographic data for series maintained by Peter Golla ().