Unconstrained Traveling Tournament Problem is APX-complete

12/18/2022

∙

by   Salomon Bendayan, et al.

∙

0

∙

share

We show that the Unconstrained Traveling Tournament Problem (UTTP) is APX-complete by presenting an L-reduction from a version of metric (1,2)-TSP to UTTP. Keywords: Traveling Tournament Problem, APX-complete, Approximation algorithms, Traveling Salesman Problem