Complexity and approximation for traveling salesman problems with profits
From MaRDI portal
Publication:2441781
DOI10.1016/j.tcs.2014.02.046zbMath1359.68114OpenAlexW1970422603MaRDI QIDQ2441781
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
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
