Improved approximation algorithm for the asymmetric prize-collecting TSP

DOI10.1007/978-3-031-16081-3_3zbMATH Open1522.90159MaRDI QIDQ6167003FDOQ6167003

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)

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

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)

Cites Work

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

Cited In (12)

• An improved approximation algorithm for the prize-collecting red-blue median problem
• Title not available (Why is that?)
• 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
• 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
• 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)