On the complexity of the traveling umpire problem

DOI10.1016/J.TCS.2014.09.037MaRDI QIDQ476848zbMATH OpenOpenAlexFDO

Authors Lucas de Oliveira, Tallys Yunes, Cid Carvalho de Souza

Publication date 2 December 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.09.037

zbMATH Keywords

computational complexitysports schedulingtraveling umpire problem

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Complexity of the traveling tournament problem
• Improved bounds for the traveling umpire problem: a stronger formulation and a relax-and-fix heuristic
• Lower bounds for large traveling umpire instances: new valid inequalities and a branch-and-cut algorithm
• Two exact algorithms for the traveling umpire problem
• Branch-and-bound with decomposition-based lower bounds for the traveling umpire problem

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An Improved Approximation Algorithm for the Traveling Tournament Problem
• Benders' cuts guided large neighborhood search for the traveling umpire problem
• Bender’s Cuts Guided Large Neighborhood Search for the Traveling Umpire Problem
• Decomposition and local search based methods for the traveling umpire problem
• Improved bounds for the traveling umpire problem: a stronger formulation and a relax-and-fix heuristic

Cited in

(8)

• Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America
• Complexity of the unconstrained traveling tournament problem
• Complexity of the traveling tournament problem
• Decomposition and local search based methods for the traveling umpire problem
• Two exact algorithms for the traveling umpire problem
• Branch-and-bound with decomposition-based lower bounds for the traveling umpire problem
• Lower bounds for large traveling umpire instances: new valid inequalities and a branch-and-cut algorithm
• Improved bounds for the traveling umpire problem: a stronger formulation and a relax-and-fix heuristic

This page was built for publication: On the complexity of the traveling umpire problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q476848)