关于旅行商问题的若干启发式算法的性能比分析

旅行商问题的增量最小插入法、最近插入法、最近加入法的性能比已经被证明有一个上界2，本文在欧几里德平面上给出了这些方法性能比接近于2的例子。另外，我们证明了凸包选边插入法的性能比有一个关于点数的对数函数上界。