@inproceedings{6f147918a7a04c7fb804567ff770bfae,

title = "The maximum traveling salesman problem under polyhedral norms",

abstract = "We consider the traveling salesman problem when the cities are points in Rd 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-2 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.",

author = "A.I. Barvinok and D.S. Johnson and G.J. Woeginger and R. Woodroofe",

year = "1998",

doi = "10.1007/3-540-69346-7_15",

language = "English",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "195--201",

editor = "R.E. Bixby and E.A. Boyd and R.Z. Rios-Mercado",

booktitle = "Integer Programming and Combinatorial Optimization (Proceedings 6th International IPCO Conference, Houston TX, USA, June 22-24, 1998)",

address = "Germany",

}