Name
Abstract | ||
|---|---|---|
This article presents a new 2-approximation algorithm for a multiple depot, multiple terminal, Hamiltonian path problem when the costs satisfy the triangle inequality. For the case where all the salesmen start from the same depot, we present another algorithm with an approximation ratio of \({\frac{5}{3}}\). These results generalize the approximation algorithms currently available for the single depot, single terminal Hamiltonian path problem. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1007/s11590-010-0252-4 | Optimization Letters |
Keywords | Field | DocType |
Traveling salesman problem, Hamiltonian path problem, Approximation algorithms | Approximation algorithm,Discrete mathematics,Mathematical optimization,Hamiltonian path,Hamiltonian path problem,Travelling salesman problem,Triangle inequality,Mathematics | Journal |
Volume | Issue | ISSN |
6 | 1 | 1862-4480 |
Citations | PageRank | References |
4 | 0.45 | 5 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jungyun Bae | 1 | 6 | 2.20 |
| Sivakumar Rathinam | 2 | 216 | 23.81 |