A LP-based approximation algorithm for generalized traveling salesperson path problem
From MaRDI portal
Publication:2150585
DOI10.1007/978-3-030-92681-6_50OpenAlexW4205700611MaRDI QIDQ2150585
Publication date: 29 June 2022
Full work available at URL: https://doi.org/10.1007/978-3-030-92681-6_50
Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Cites Work
- Shorter tours by nicer ears: \(7/5\)-approximation for the graph-TSP, \(3/2\) for the path version, and \(4/3\) for two-edge-connected subgraphs
- Testing membership in matroid polyhedra
- The ellipsoid method and its consequences in combinatorial optimization
- Analysis of Christofides' heuristic: some paths are more difficult than cycles
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- The traveling salesman problem and its variations
- Approximation algorithms for general cluster routing problem
- \(\frac{13}{9}\)-approximation for graphic TSP
- Traveling salesman path problems
- Improving Christofides' Algorithm for the s-t Path TSP
- Removing and Adding Edges for the Traveling Salesman Problem
- P-Complete Approximation Problems
- Approximation Algorithms for Some Postman Problems
- Matching, Euler tours and the Chinese postman
- Eight-Fifth Approximation for the Path TSP
- Reducibility among Combinatorial Problems
- The Salesman’s Improved Paths through Forests
- A 1.5-Approximation for Path TSP
- Approaching 3/2 for the s - t -path TSP
- Solution of a Large-Scale Traveling-Salesman Problem
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Matroids and the greedy algorithm
- A (slightly) improved approximation algorithm for metric TSP
