Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio

DOI10.1007/978-3-031-22543-7_6zbMath1528.90221OpenAlexW4313407184MaRDI QIDQ6169113

Ksenia Rizhenko, Mikhail Yu. Khachay, Katherine Neznakhina

Publication date: 10 August 2023

Published in: Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-031-22543-7_6

zbMATH Keywords

asymmetric TSPprize-collecting traveling salesman problemapproximation with constant ratio

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the prize collecting traveling salesman problem
• The Euclidean traveling salesman problem is NP-complete
• A unified matheuristic for solving multi-constrained traveling salesman problems with profits
• The traveling salesman problem and its variations.
• Optimization for drone and drone-truck combined operations: a review of the state of the art and future directions
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• A branch-and-cut algorithm for the undirected prize collecting traveling salesman problem
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
• The prize collecting traveling salesman problem
• On some connectivity properties of Eulerian graphs
• P-Complete Approximation Problems
• A General Approximation Technique for Constrained Forest Problems
• A Branch-and-Cut and MIP-based heuristics for the Prize-Collecting Travelling Salesman Problem
• An improved approximation algorithm for ATSP
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem