A primal-dual approximation algorithm for the asymmetric prize-collecting TSP

DOI10.1007/s10878-012-9501-zzbMath1268.90070OpenAlexW2117443767MaRDI QIDQ1944387

Viet Hung Nguyen

Publication date: 25 March 2013

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-012-9501-z

zbMATH Keywords

approximation algorithmprimal-dual algorithmprize collecting traveling salesman

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items (1)

Improved approximation algorithm for the asymmetric prize-collecting TSP

Cites Work

• A note on the prize collecting traveling salesman problem
• Approximating the asymmetric profitable tour
• The prize collecting traveling salesman problem
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• A General Approximation Technique for Constrained Forest Problems
• Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem

This page was built for publication: A primal-dual approximation algorithm for the asymmetric prize-collecting TSP