Improved approximation algorithm for the asymmetric prize-collecting TSP

DOI10.1007/978-3-031-16081-3_3MaRDI QIDQ6167003zbMATH OpenFDO

Authors Bo Hou, Zhenzhen Pang, Suogang Gao, Wen Liu

Publication date 7 July 2023

Published in Algorithmic Aspects in Information and Management (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmasymmetric prize-collecting traveling salesman problem

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Approximating the asymmetric profitable tour
• Approximating the asymmetric profitable tour

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A note on the prize collecting traveling salesman problem
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• Approximating the asymmetric profitable tour
• Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem

Cited in

(12)

• An improved approximation algorithm for the prize-collecting red-blue median problem
• scientific article; zbMATH DE number 6297719 (Why is no real title available?)
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• Approximating the asymmetric profitable tour
• Improved large-step Markov chain variants for the symmetric TSP
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• An \(O(\log n/ \log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio
• An \(O(\log n/\log \log n)\)-approximation algorithm for the asymmetric traveling salesman problem
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• Approximating the asymmetric profitable tour
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP

This page was built for publication: Improved approximation algorithm for the asymmetric prize-collecting TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6167003)