【摘要】 旅行推销员问题(TSP)邻近算法的性能比已经被证明有一个关于点数的对数函数上界,本文就该方法在欧几里得平面上给出了性能比的一个对数下界。更多还原

【Abstract】 The performance ratio of the nearest neighbor algorithm of traveling salesman problem has been shown to have an upper bound above by a logarithmic function of the number of nodes. In this paper, we provide a logarithmic lower bound on the worst case in Euclidean plane.更多还原