Loading...
Please wait, while we are loading the content...
Similar Documents
The maximum traveling salesman problem under polyhedral norms (1998).
| Content Provider | CiteSeerX |
|---|---|
| Author | Barvinok, Alexander Johnson, David S. Woeginger, Gerhard J. Woodroofe, Russell |
| Abstract | . We consider the traveling salesman problem when the cities are points in R d for some fixed d and distances are computed according to a polyhedral norm. We show that for any such norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O(n f \Gamma2 log n), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus for example we have O(n 2 log n) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. 1 Introduction In the Traveling Salesman Problem (TSP), the input consists of a set C of cities together with the distances d(c; c 0 ) between every pair of distinct cities c; c 0 2 C. The goal is to find an ordering or tour of the cities that minimizes (Minimum TSP) or maximizes (Maximum TSP) the total tour leng... |
| File Format | |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Polyhedral Norm Maximum Traveling Salesman Problem Salesman Problem Minimum Tsp Maximum Length Distinct City Minimum Length Tour Polynomial Time Traveling Salesman Problem Unit Time Gamma2 Log Sup Norm Arithmetic Operation Maximum Tsp Algorithm Run Total Tour Leng |
| Content Type | Text |
