Back to Search
Start Over
An LP-based approximation algorithm for the generalized traveling salesman path problem.
- Source :
-
Theoretical Computer Science . Jan2023, Vol. 941, p180-190. 11p. - Publication Year :
- 2023
-
Abstract
- The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 941
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 160820041
- Full Text :
- https://doi.org/10.1016/j.tcs.2022.11.013