Complexity and approximation for traveling salesman problems with profits
From MaRDI portal
Publication:2441781
DOI10.1016/j.tcs.2014.02.046zbMath1359.68114MaRDI 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
68Q25: Analysis of algorithms and problem complexity
90C60: Abstract computational complexity for mathematical programming problems
90C27: Combinatorial optimization
68W25: Approximation algorithms
Related Items
Solving the probabilistic profitable tour problem on a line, A revisited branch-and-cut algorithm for large-scale orienteering problems, The capacitated orienteering problem, The bi-objective insular traveling salesman problem with maritime and ground transportation costs, An LP-based approximation algorithm for the generalized traveling salesman path 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
