The Traveling Saleman Problem with Many Visits to Few Cities
We study the version of the traveling salesman problem in which a relatively small number of cities -- say, six -- must be visited a huge number of times -- e.g., several hundred times each. )It costs to go from one city to itself). We develop an algorithm for this problem whose running time is expo...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149019 |
| _version_ | 1811070873942097920 |
|---|---|
| author | Cosmadakis, Stavros S. Papadimitriou, Christos H. |
| author_facet | Cosmadakis, Stavros S. Papadimitriou, Christos H. |
| author_sort | Cosmadakis, Stavros S. |
| collection | MIT |
| description | We study the version of the traveling salesman problem in which a relatively small number of cities -- say, six -- must be visited a huge number of times -- e.g., several hundred times each. )It costs to go from one city to itself). We develop an algorithm for this problem whose running time is exponential in the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems. |
| first_indexed | 2024-09-23T08:43:02Z |
| id | mit-1721.1/149019 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T08:43:02Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1490192023-03-30T04:18:51Z The Traveling Saleman Problem with Many Visits to Few Cities Cosmadakis, Stavros S. Papadimitriou, Christos H. We study the version of the traveling salesman problem in which a relatively small number of cities -- say, six -- must be visited a huge number of times -- e.g., several hundred times each. )It costs to go from one city to itself). We develop an algorithm for this problem whose running time is exponential in the number of cities, but logarithmic in the number of visits. Our algorithm is a practical approach to the problem for instances of size in the range indicated above. The implementation and analysis of our algorithm give rise to a number of interesting graph-theoretic and counting problems. 2023-03-29T14:20:06Z 2023-03-29T14:20:06Z 1981-11 https://hdl.handle.net/1721.1/149019 9143736 MIT-LCS-TM-208 application/pdf |
| spellingShingle | Cosmadakis, Stavros S. Papadimitriou, Christos H. The Traveling Saleman Problem with Many Visits to Few Cities |
| title | The Traveling Saleman Problem with Many Visits to Few Cities |
| title_full | The Traveling Saleman Problem with Many Visits to Few Cities |
| title_fullStr | The Traveling Saleman Problem with Many Visits to Few Cities |
| title_full_unstemmed | The Traveling Saleman Problem with Many Visits to Few Cities |
| title_short | The Traveling Saleman Problem with Many Visits to Few Cities |
| title_sort | traveling saleman problem with many visits to few cities |
| url | https://hdl.handle.net/1721.1/149019 |
| work_keys_str_mv | AT cosmadakisstavross thetravelingsalemanproblemwithmanyvisitstofewcities AT papadimitriouchristosh thetravelingsalemanproblemwithmanyvisitstofewcities AT cosmadakisstavross travelingsalemanproblemwithmanyvisitstofewcities AT papadimitriouchristosh travelingsalemanproblemwithmanyvisitstofewcities |