Optimization Online


On the Complexity of the Traveling Umpire Problem

Lucas de Oliveira (lucas.oliveira***at***ic.unicamp.br)
Cid de Souza (cid***at***ic.unicamp.br)
Tallys Yunes (tallys***at***miami.edu)

Abstract: The traveling umpire problem (TUP) consists of determining which games will be handled by each one of several umpire crews during a double round-robin tournament. The objective is to minimize the total distance traveled by the umpires, while respecting constraints that include visiting every team at home, and not seeing a team or venue too often. Even small instances of the TUP are very difficult to solve, and several exact and heuristic approaches for it have been proposed in the literature. To this date, however, no formal proof of the TUP's computational complexity exists. We prove that the decision version of the TUP is NP-Complete for certain values of its input parameters.

Keywords: traveling umpire problem, computational complexity, sports scheduling

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Other )

Category 3: Other Topics (Other )

Citation: Article published in Theoretical Computer Science at www.sciencedirect.com/science/article/pii/S0304397514007270


Entry Submitted: 05/07/2014
Entry Accepted: 05/07/2014
Entry Last Modified: 09/23/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society