The maximum traveling salesman problem under polyhedral norms

A.I. Barvinok, D.S. Johnson, G.J. Woeginger, R. Woodroofe

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    32 Citaten (Scopus)


    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.
    Originele taal-2Engels
    TitelInteger Programming and Combinatorial Optimization (Proceedings 6th International IPCO Conference, Houston TX, USA, June 22-24, 1998)
    RedacteurenR.E. Bixby, E.A. Boyd, R.Z. Rios-Mercado
    Plaats van productieBerlin
    StatusGepubliceerd - 1998

    Publicatie series

    NaamLecture Notes in Computer Science
    ISSN van geprinte versie0302-9743


    Duik in de onderzoeksthema's van 'The maximum traveling salesman problem under polyhedral norms'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit