Clarkson的2-近似加權頂點覆蓋算法運行時分析

Question

一個衆所周知的2-近似爲最小加權頂點覆蓋問題是由克拉克森提出的一個：

克拉克森，肯尼斯L.「貪婪算法的修改頂點覆蓋「。信息處理快報16.1（1983）：23-25。

易於閱讀的算法僞代碼可以找到here請參閱第32.1.2節。根據論文，該算法的運行時間複雜度爲O(|E|*log|V|)，其中E是邊的集合，V是頂點的集合。我不完全確定他們是如何得到這個結果的。設d（v）爲圖中頂點v的度數，w（v）爲權重函數。 排除一些從算法的技術性的，該算法是這樣的：

while(|E| != 0){ //While there are still edges in the graph 
    Pick a vertex v \in V for which w(v)/d(v) is minimized; 
    for(u : (u,v) \in E){ 
     update w(u); 
     ... 
    } 
    delete v and all edges incident to it from the graph. 
} 

外環產生在運行復雜度的術語|E|。這意味着從頂點列表中挑選一個頂點，使頂點的比例最小化可以在log n時間內完成。據我所知，從值列表中找出最小值需要n-1比較，而不是log n。最後，for循環的內部循環針對v的每個鄰居運行，因此產生由n-1支配的d（v）的複雜度。因此我會斷定該算法的運行時複雜度爲O(|E|*|V|)。 我在這裏錯過了什麼？

Answer 1

將頂點保留在按w（v）/ d（v）排序的平衡二叉搜索樹中。找到最小值是O（log | V |）。每次我們刪除邊緣uv時，我們都必須更新u的密鑰（通過刪除它並將它重新插入到具有新密鑰的樹中），這需要花費時間O（log | V |）。這些步驟中的每一步都最多完成| E |倍。