Unconstrained Traveling Tournament Problem is APX-complete
2022
Online
report
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
Comment: The results of this paper appear in preliminary form in the thesis of the first author "The Traveling Tournament Problem'', Master's thesis, University of Waterloo, 2022. See: https://uwspace.uwaterloo.ca/handle/10012/18553
Titel: |
Unconstrained Traveling Tournament Problem is APX-complete
|
---|---|
Autor/in / Beteiligte Person: | Bendayan, Salomon ; Cheriyan, Joseph ; Cheung, Kevin K. H. |
Link: | |
Veröffentlichung: | 2022 |
Medientyp: | report |
Schlagwort: |
|
Sonstiges: |
|