期刊论文、会议论文

Fu, Bin

英文

Lecture Notes in Computer Science

0302-9743

2019

11640

121-128

13th International Conference on Algorithmic Aspects in Information and Management, AAIM 2019

Algorithmic Aspects in Information and Management

6 August 2019 through 8 August 2019

Beijing, PEOPLES R CHINA

[Chen, Zhixiang;Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.^[Feng, Qilong;Wang, Jianxin] Cent Southern Univ, Sch Informat, Changsha, Peoples R China.^[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.

Ding-Zhu Du<&wdkj&>Lian Li<&wdkj&>Xiaoming Sun<&wdkj&>Jialin Zhang

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

Springer Verlag

9783030271947

10.1007/978-3-030-27195-4_11

The authors would like to thank the reviewers whose suggestions improve the presentation of this paper. This research is supported by NSFC 61772179, 61872450 and Hunan Provincial Natural Science Foundation 2019JJ40005.

本校为其他机构

In this paper, we develop an exponential time approximation scheme for the traveling salesman problem (TSP) on undirected graphs. If the weight of each edge is a nonnegative real number, then there is an algorithm to give an (1 + ϵ) approximation for the TSP problem in O(1/ϵ·1.66n) and a polynomial space. It is in contrast to Golovnen’s approximation scheme for TSP on directed graphs with O(1/ϵ·2n) time. We also show that there is no 2o(n) time constant factor approximation for the TSP problem under Exponential Time Hyp...