Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/241597
Type: Artigo
Title: On the complexity of the traveling umpire problem
Author: Oliveira, Lucas de
Souza, Cid C. de
Yunes, Tallys
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. (C) 2014 Elsevier B.V. All rights reserved.
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 co
Subject: Complexidade computacional
Otimização combinatória
Esportes - Planejamento
Country: Países Baixos
Editor: Elsevier
Citation: On The Complexity Of The Traveling Umpire Problem. Elsevier Science Bv, v. 562, p. 101-111 Jan-2015.
Rights: embargo
Fechado
Identifier DOI: 10.1016/j.tcs.2014.09.037
Address: https://www.sciencedirect.com/science/article/pii/S0304397514007270
Date Issue: 2015
Appears in Collections:IC - Artigos e Outros Documentos

Files in This Item:
File SizeFormat 
000347602000008.pdf427.22 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.