algorithm - TSP メトリックの近似の証明

Question

次の質問に行き詰まりました。

次のヒューリスティックを考えてみましょう: 頂点を 1 つだけ含むツアーから開始します。各ステップで、ツアーの頂点までの距離が短いツアーの外側の頂点を見つけます。v を外側の頂点、u を内側の頂点とします。ツアーの u の直後に v を追加します。エッジが三角形の距離プロパティに従うとします。このヒューリスティックが TSP メトリック問題の 2 近似であることをどのように示すことができますか?

誰もそれを開始する方法を知っていますか?

前もって感謝します

Answer 1

明らかに、証明することは不可能です。説明されているアルゴリズムは2 近似ではありません。ウィキペディアの記事では、出版物について言及しています

Rosenkrantz、Daniel J.; スターンズ、リチャードE。ルイス、フィリップ M.、II (1977)、「巡回セールスマン問題に対するいくつかのヒューリスティックの分析」、コンピューティングに関する SIAM ジャーナル 6 (5): 563–581、doi:10.1137/0206041

どうやら著者は、インスタンスが三角形の不等式を満たしている場合でも、Nearest Neighbor ヒューリスティックが の近似比を生成することを示していますTheta( log n )。ここで、 は位置の数です。n

ローゼンクランツ等。[1977] は、NN アルゴリズムが三角形の不等式を満たすインスタンスの近似係数 Theta(log|V|) を持つことを示しました。

ただし、OP は別のアルゴリズムを記述している可能性があります。さまざまな貪欲なヒューリスティックの近似比の分析は、次の記事で見つけることができます。

コンピューティングに関する SIAM ジャーナル、1977 年、Vol. 6, No. 3 : pp. 563-581 巡回セールスマン問題に対するいくつかのヒューリスティックスの分析 Rosenkrantz, D., Stearns, R., and Lewis, II, P. (doi: 10.1137/0206041)