The geometric maximum traveling salesman problem
From MaRDI portal
Publication:3452505
DOI10.1145/876638.876640zbMath1325.90074arXivcs/0204024OpenAlexW2085110997MaRDI QIDQ3452505
Arie Tamir, Gerhard J. Woeginger, Sándor P. Fekete, Russ Woodroofe, David S. Johnson, Alexander I. Barvinok
Publication date: 12 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0204024
optimizationtraveling salesman problempolynomial timeNP-hardnessEuclidean metricmaximum scatter TSPpolyhedral metric
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension, An algorithm for the polyhedral cycle cover problem with constraints on the number and length of cycles, A quantization framework for smoothed analysis of Euclidean optimization problems, Winding indexes of Max. and Min. Hamiltonians in N-Gons, Asymptotically optimal algorithms for geometric MAX TSP and MAX \(m\)-PSP, On the probabilistic behaviour of a heuristic algorithm for maximal Hamiltonian tours, Geometric versions of the three-dimensional assignment problem under general norms, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, On the longest spanning tree with neighborhoods
