FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM

DOI10.15826/umj.2023.1.012OpenAlexW4385348864MaRDI QIDQ6081704

Mikhail Yu. Khachay, Unnamed Author, Katherine Neznakhina

Publication date: 5 October 2023

Published in: Ural Mathematical Journal (Search for Journal in Brave)

Full work available at URL: http://mathnet.ru/eng/umj194

zbMATH Keywords

approximation algorithmtriangle inequalityprize-collecting traveling salesman problemfixed approximation ratio

Mathematics Subject Classification ID

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

Related Items

Approximation algorithms with constant factors for a series of asymmetric routing problems ⋮ Polynomial-time approximability of the asymmetric problem of covering a graph by a bounded number of cycles

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
• Efficient approximation of the metric CVRP in spaces of fixed doubling dimension
• 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
• The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme
• 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
• Reducing Curse of Dimensionality
• 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
• Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm