@online{Saller2311.00604,
TITLE = {A Systematic Review of Approximability Results for Traveling Salesman Problems leveraging the {TSP}-{T3CO} Definition Scheme},
AUTHOR = {Saller, Sophia and Koehler, Jana and Karrenbauer, Andreas},
LANGUAGE = {eng},
URL = {https://arxiv.org/abs/2311.00604},
EPRINT = {2311.00604},
EPRINTTYPE = {arXiv},
YEAR = {2024},
MARGINALMARK = {$\bullet$},
ABSTRACT = {The traveling salesman (or salesperson) problem, short TSP, is a problem of<br>strong interest to many researchers from mathematics, economics, and computer<br>science. Manifold TSP variants occur in nearly every scientific field and<br>application domain: engineering, physics, biology, life sciences, and<br>manufacturing just to name a few. Several thousand papers are published on<br>theoretical research or application-oriented results each year. This paper<br>provides the first systematic survey on the best currently known<br>approximability and inapproximability results for well-known TSP variants such<br>as the "standard" TSP, Path TSP, Bottleneck TSP, Maximum Scatter TSP,<br>Generalized TSP, Clustered TSP, Traveling Purchaser Problem, Profitable Tour<br>Problem, Quota TSP, Prize-Collecting TSP, Orienteering Problem, Time-dependent<br>TSP, TSP with Time Windows, and the Orienteering Problem with Time Windows. The<br>foundation of our survey is the definition scheme T3CO, which we propose as a<br>uniform, easy-to-use and extensible means for the formal and precise definition<br>of TSP variants. Applying T3CO to formally define the variant studied by a<br>paper reveals subtle differences within the same named variant and also brings<br>out the differences between the variants more clearly. We achieve the first<br>comprehensive, concise, and compact representation of approximability results<br>by using T3CO definitions. This makes it easier to understand the<br>approximability landscape and the assumptions under which certain results hold.<br>Open gaps become more evident and results can be compared more easily.<br>},
}