Approximating the asymmetric profitable tour

MaRDI QIDQ2861509zbMATH OpenFDO

Authors Viet Hung Nguyen, Thi Thu Thuy Nguyen

Publication date 8 November 2013

Full work available at URL http://www.sciencedirect.com/science/article/pii/S1571065310001162

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Approximating the asymmetric profitable tour
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• Improved approximation algorithm for the asymmetric prize-collecting TSP

Cites work

• A 2log2(n)-Approximation Algorithm for Directed Tour Cover
• A note on the prize collecting traveling salesman problem
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• scientific article; zbMATH DE number 432785 (Why is no real title available?)
• On Prize‐collecting Tours and the Asymmetric Travelling Salesman Problem
• On some connectivity properties of Eulerian graphs
• On the worst-case performance of some algorithms for the asymmetric traveling salesman problem
• Some remarks on Arc‐connectivity, vertex splitting, and orientation in graphs and digraphs
• The prize collecting traveling salesman problem

Cited in

(11)

• Approximating the minimum tour cover of a digraph
• Approximating the asymmetric profitable tour
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• The multi-vehicle profitable pickup and delivery problem
• A primal-dual approximation algorithm for the asymmetric prize-collecting TSP
• Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests
• Exact methods for solving the elementary shortest and longest path problems
• Solving the probabilistic profitable tour problem on a line
• FIXED RATIO POLYNOMIAL TIME APPROXIMATION ALGORITHM FOR THE PRIZE-COLLECTING ASYMMETRIC TRAVELING SALESMAN PROBLEM
• Improved approximation algorithm for the asymmetric prize-collecting TSP
• Prize-collecting asymmetric traveling salesman problem admits polynomial time approximation within a constant ratio

This page was built for publication: Approximating the asymmetric profitable tour

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