一千萬個為什麽

搜索

關於獎勵收集TSP的比率與inapprox相關的問題。一般TSP

獎品收集TSP(PCTSP)被定義為普通TSP,不同之處在於懲罰被添加到節點;所以我們可能會避免訪問支付其罰款的節點,這會增加到總成本中。它目前承認$ 2 \ epsilon $近似比率,其邊緣成本被認為滿足三角不等式。顯然,普通TSP是PCTSP,其中所有節點懲罰都設置為inf。

我想問一下,如果選擇了不滿足三角形不等式的圖形並且刪除了所有邊緣,則將每個刪除邊緣情況下連接到2度新節點的2個新邊緣替換為每個邊緣。邊緣成本等於刪除邊緣的成本/ 2並且歐幾裏德距離等於(因此新圖形是公制),我們不能獲得原始的$(2 \ epsilon)$近似比率(一般因此不可近似的圖? (舊節點的懲罰設置為inf,新的2度節點設置為0)。

當然,我的想法有一個錯誤,因為這不可能是真的,所以如果有人發現它,我會很高興聽到這個。先謝謝你。

最佳答案

編輯可以回答,我希望現在變得更清楚(或者我發現我不明白的東西):

你的過程如下:如果你有一個邊緣$ e = \ {u,v \} $,權重為$ t $,你將$ e $替換為長度為2的路徑,邊緣為$ \ {u,z_e \} $和$ \ {z_e,v \} $。 $ z_e $是一個新節點,兩個新邊緣中的每一個都獲得權重$ t/2 $。對於每個邊緣,我們引入一個新節點。

到目前為止,我們沒有公制實例,因為到目前為止$ u $和$ v $之間沒有優勢,$ u $和$ v $之間的距離是無限的。因此,您采用最短路徑度量來獲取這些距離。 (我想這就是“歐幾裏德距離等於”的意思。否則,你應該澄清一下。)

我的觀點是,根據最短路徑度量添加距離後,$ u $和$ v $之間的距離可能不再是$ t $,因此您無法獲得原始實例: 考慮邊長為$ 1 $,$ 1 $和$ t $的三角形。讓$ u $和$ v $成為權重$ t $的邊緣節點。應用你的建築。 $ u $和$ v $之間的最短路徑是$ 2 $(它需要4個邊緣,權重$ 1/2 $)而不是$ t $。

順便說一句:歐幾裏德距離應該只是問題中的距離。

轉載註明原文: 關於獎勵收集TSP的比率與inapprox相關的問題。一般TSP