期刊论文、会议论文

Fu, Bin

英文

Lecture Notes in Computer Science

0302-9743

2019

11640

121-128

13th International Conference on Algorithmic Aspects in Information and Management (AAIM)

Lecture Notes in Computer Science

AUG 06-08, 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.

Du, DZ Li, L Sun, X Zhang, J

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

978-3-030-27195-4; 978-3-030-27194-7

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

NSFCNational Natural Science Foundation of China (NSFC) [61772179, NSFC 61872450]; Hunan Provincial Natural Science FoundationNatural Science Foundation of Hunan Province [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+\epsilon )\) approximation for the TSP problem in \(O({1\over \epsilon }\cdot 1.66^n)\) and a polynomial space. It is in contrast to Golovnen’s approximation scheme for TSP on directed graphs with \(\mathrm{O}({1\over \epsilon }\cdot 2^n)\) time. We also show that there is no \(2^{o(n)}\) time constant factor approximation for th...