旅行推销员问题凸包方法的性能比分析

在欧几里德平面上证明了旅行推销员问题的凸包方法的性能比上界为n／2，同时给出了凸包随意插入算法的性能比可以接近n／2的例子。另外，对凸包增量最小插入法、凸包最近插入法及凸包最近加入法给出了性能比不超过3的证明。