Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension

作     者：Shenmaier, Vladimir 

作者机构：Sobolev Inst Math Novosibirsk Russia 

出 版 物：《OPTIMIZATION LETTERS》 (最优化通信)

年 卷 期：2022年第16卷第7期

页      面：2115-2122页

核心收录：

学科分类：0810[工学-信息与通信工程] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 08[工学] 070104[理学-应用数学] 081001[工学-通信与信息系统] 0701[理学-数学] 

基　　金：Sobolev Institute of Mathematics [0314-2019-0014] 

主　　题：Max TSP Metric space Doubling dimension Efficient PTAS Asymptotically exact algorithm 

摘      要：The maximum traveling salesman problem (Max TSP) consists of finding a Hamiltonian cycle with the maximum total weight of the edges in a given complete weighted graph. This problem is APX-hard in the general metric case but admits polynomial-time approximation schemes in the geometric setting, when the edge weights are induced by a vector norm in fixed-dimensional real space. We propose the first approximation scheme for Max TSP in an arbitrary metric space of fixed doubling dimension. The proposed algorithm implements an efficient PTAS which, for any fixed epsilon is an element of (0,1), computes a (1 - epsilon)-approximate solution of the problem in cubic time. Additionally, we suggest a cubic-time algorithm which finds asymptotically optimal solutions of the metric Max TSP in fixed and sublogarithmic doubling dimensions.