A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme

Sophia Saller (), Jana Koehler () and Andreas Karrenbauer ()
Additional contact information
Sophia Saller: Deutsches Forschungszentrum für Künstliche Intelligenz
Jana Koehler: Lucerne University of Applied Sciences and Arts
Andreas Karrenbauer: Max Planck Institute for Informatics

Annals of Operations Research, 2025, vol. 351, issue 3, No 12, 2129-2190

Abstract: Abstract The traveling salesman (or salesperson) problem, short TSP, is of strong interest to many researchers from mathematics, economics, and computer science. Manifold TSP variants occur in nearly every scientific field and application domain: e.g., engineering, physics, biology, life sciences, and manufacturing. Several thousand papers are published every year. This paper provides the first systematic survey on the best currently known approximability and inapproximability results for well-known TSP variants such as the “standard”, Path, Bottleneck, Maximum Scatter, Generalized, Clustered, Quota, Prize-Collecting, Time-dependent TSP, Traveling Purchaser Problem, Profitable Tour Problem, Orienteering Problem, TSP with Time Windows, and Orienteering Problem with Time Windows. The foundation of our survey is the definition scheme TSP-T3CO , which we propose as a uniform, easy-to-use and extensible means for the formal and precise definition of TSP variants. Applying TSP-T3CO to define a TSP variant reveals subtle differences within the same named variant and also brings out the differences between variants more clearly. We achieve the first comprehensive, concise, and compact representation of approximability results by using TSP-T3CO definitions. This makes it easier to understand the approximability landscape and the assumptions under which certain results hold. Open gaps become more evident and results can be compared more easily. Graphical abstract

Keywords: Traveling Salesperson; Traveling Salesman; Definition scheme; Polynomial-time approximation algorithms (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-025-06641-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:351:y:2025:i:3:d:10.1007_s10479-025-06641-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-025-06641-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().