TSP 启发式 - 最坏情况比率

TSP Heuristics - Worst case ratio

我在尝试总结这些启发式算法的最坏情况比率时遇到了一些麻烦（这意味着它满足三角不等式）旅行商问题：

最近的邻居：

Here 它表示 NN 的 w-C 比率为

This one, page 8, same as this one说是

变化很大。

插入算法： 非常匹配每个人都同意最便宜和最近插入的 w-c 比率 <= 2（总是只是为了满足三角不等式的实例）但是每个来源的最远插入都是不同的：

here:

（忘记把NN改成FI）

同时 here 是

和here还有一个不一样的：

关于FI，我觉得还是要看首发的子游。 但在 NN 中，那个 ceil 或 floor 括号会改变很多结果，而且由于它们都来自良好的来源，我无法理解选对了。

有人可以总结这些算法实际已知的最坏情况比率吗？

NN：正确的界限使用上限，而不是下限（至少如 Rosenkrantz 等人在原始论文中所证明的那样 - here，如果您有权访问）。我认为最近没有使用 floor 的界限。

FI：Rosenkrantz 等人。证明第一个边界适用于 any 插入启发式算法，包括 NN。此外，该界限优于其他两个界限（除了非常小的 n）。所以我会使用那个绑定。但是请注意，log 在该公式中实际上意味着 log_2。 （我不确定其他两个边界是从哪里来的。）

另一个注意事项：众所周知，NN 存在 nofixed 最坏情况边界。 不知道 FI 是否有固定的最坏情况界限。