Loading...
Please wait, while we are loading the content...
Similar Documents
Finding Maximum Length Tours Under Polyhedral Norms (1998)
| Content Provider | CiteSeerX |
|---|---|
| Author | Barvinok, Alexander Johnson, David S. Woeginger, Gerhard J. Woodroofe, Russell |
| Description | Proceedings of IPCO VI, Lecture Notes in Computer Science 1412 We consider the traveling salesman problem when the cities are points in IR 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+1 ), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus for example we have O(n 5 ) 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. Keywords: Traveling salesman problem, combinatorial optimization, polyhedral norm, b-matching, computational complexity. AMS 1991 subject classification: 90C27. barvinok@math.lsa.umich.edu. University of Michigan, Dept. of Mathematics, Ann Arbor, MI 48109-1009, USA. Supported by an Alfred P. Sloan Research Fellowship and by NS... |
| File Format | |
| Language | English |
| Publisher | Springer |
| Publisher Date | 1998-01-01 |
| Access Restriction | Open |
| Subject Keyword | Subject Classification Minimum Length Tour Maximum Length Tour Ann Arbor Salesman Problem Barvinok Math Unit Time Arithmetic Operation Sup Norm Sloan Research Fellowship Combinatorial Optimization Maximum Length Polyhedral Norm Algorithm Run Polynomial Time Computational Complexity |
| Content Type | Text |
| Resource Type | Article |
