An LP-based approximation algorithm for the generalized traveling salesman path problem

DOI10.1016/j.tcs.2022.11.013OpenAlexW4309336419MaRDI QIDQ2680860

Yanyan Li

Publication date: 4 January 2023

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

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

zbMATH Keywords

TSPapproximation algorithmLP roundinggeneralized traveling salesman path problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traveling salesman problems in temporal graphs
• 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 via contraction decomposition
• Approximation of the double traveling salesman problem with multiple stacks
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• \(\frac{13}{9}\)-approximation for graphic TSP
• Complexity and approximation for traveling salesman problems with profits
• Traveling salesman path problems
• On the approximability of the traveling salesman problem
• Reassembling Trees for the Traveling Salesman
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Removing and Adding Edges for the Traveling Salesman Problem
• Better s-t-Tours by Gao Trees
• 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
• Improving christofides' algorithm for the s-t path TSP
• Contraction decomposition in h-minor-free graphs and algorithmic applications
• A Randomized Rounding Approach to the Traveling Salesman Problem
• Matroids and the greedy algorithm
• A (slightly) improved approximation algorithm for metric TSP