Complexity and approximation for traveling salesman problems with profits

DOI10.1016/j.tcs.2014.02.046zbMath1359.68114OpenAlexW1970422603MaRDI QIDQ2441781

Yanyan Li

Publication date: 28 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.02.046

zbMATH Keywords

treecomputational complexitycycleapproximation algorithmpathrouting problem with profit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (5)

The bi-objective insular traveling salesman problem with maritime and ground transportation costs ⋮ Solving the probabilistic profitable tour problem on a line ⋮ A revisited branch-and-cut algorithm for large-scale orienteering problems ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ The capacitated orienteering problem

Cites Work

• Unnamed Item
• A note on the prize collecting traveling salesman problem
• A constant-factor approximation algorithm for the \(k\)-MST problem
• Primal-dual approximation algorithms for the prize-collecting Steiner tree problem
• A \(2+\varepsilon\) approximation algorithm for the \(k\)-MST problem
• Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Improved algorithms for orienteering and related problems
• Approximation algorithms for deadline-TSP and vehicle routing with time-windows
• Saving an epsilon
• New Approximation Guarantees for Minimum-Weight k-Trees and Prize-Collecting Salesmen
• A General Approximation Technique for Constrained Forest Problems
• Reducibility among Combinatorial Problems
• Approximation Algorithms for Orienteering and Discounted-Reward TSP
• Algorithms - ESA 2003
• Steiner Tree Problems With Profits

This page was built for publication: Complexity and approximation for traveling salesman problems with profits