一個最小集合覆蓋訣竅演算法的改良與分析

An Improvement and Analysis of a Heuristic Algorithm of the Minimum Set Covering Problem

洪孟琮(Mong-Chung Hung)

指導教授 ： 林華君

國立清華大學/電機資訊學院/通訊工程研究所/碩士(2007年)

摘要

在我們之前有關Link Failure Detection的研究，提出了一個求解Minimum Set Covering Problem的Heuristic Algorithm。Minimum Set Covering Problem是一個常見的問題，在各方面都有廣泛的應用。我門之前的研究，證實了此Algorithm在求解由Link Failure Detection所產生的Minimum Set Covering Problem時，具有比Greedy Algorithm更好的效果。然而，我們並沒有針對它與其他類似的演算法進行更深入的分析及比較，且其時間複雜度亦過高。

本篇論文對此Heuristic Algorithm提出了改良的方法，使其worst cast time complexity由O(min(|X|,|F|))*O(|F|)*O(|F|)*O(|X|)降低為O(min(|X|,|F|))*O(|F|)*O(|X|)，並且整理出與此方法類似的Greedy based algorithms，包含Greedy Algorithm、TGreedy Algorithm以及AltGreedy Algorithm[6]。我們以各種不同的方式產生了Minimum Set Covering Problems，包含由Link Failure Detection問題所形成的Minimum Set Covering Problem[1]、OR-Library[9]，以及由各種不同參數所產生的Random Problems。

針對這些algorithms以及各種不同類型的Minimum Set Covering Problem，我們做了完整的模擬測試，從模擬的結果可以觀察出我們先前所提出的Heuristic Algorithm，不僅在求解由Link Failure Detection所產生的Minimum Set Covering Problem時有很好的效果，對於一般性的Minimum Set Covering Problem，也能求得比其他方法更好的解。

另外，本篇論文針對此Heuristic Algorithm以及其他類似的algorithms，也做了worst case time complexity的分析，由分析的結果以及模擬的結果，我們發現TGreedy演算法的最差情況時間複雜度最高，AltGreedy演算法次之，Greedy演算法最小。而我們所提出的Heuristic Algorithm，在本篇論文的改良前，其最差情況時間複雜度與AltGreedy演算法相同。在本篇論文的改良後，其最差情況時間複雜度則降低至與Greedy演算法相同。

關鍵字

最小集合覆蓋演算法 ； 異常管理 ； 連結錯誤偵測 ； 訣竅演算法 ； 網路管理

並列摘要

We have proposed a heuristic algorithm of the minimal set covering problem in our previous work about the Link Failure Detection, and proved that the algorithm is superior to the Greedy algorithm in solving the minimal set covering problem incurred from the Link Failure Detection.
In this paper, we proposed an improvement of the heuristic algorithm, lowering its worst cast time complexity from the order of 3 to the order of 2. Also, we surveyed the Greedy based heuristic algorithms of the minimal set covering problem, which are similar to our heuristic algorithm, applied thorough simulation to prove that the heuristic algorithm we proposed is superior to all the other greedy based heuristic algorithms in various kind of minimal set covering problems.

並列關鍵字

set cover ； fault management ； link failure detection ； heuristic algorithm ； network management

參考文獻

【1】 Hwa-Chun Lin, Chien-Hsing Wang, Lung-Chih Tung, Minimizing the Number of Detectors in Distributed Poll-Based Link Failure Detection and Identification

【2】 Garfinkel,R.S. and Nemhauser, G. L. , Integer Programming. John Wiley & Sons, New York.

【3】 Karp, R. M,Reducibility among Combinatorial Problems. In: Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, eds. Plenum Press, New York.

【4】 Harvey M. Salkin and Ronald D. Koncal, Set Covering by an All Integer Algorithm: Computational Experience

【6】 Tal Grossman, Avishai Wool,Computational Experience with Approximation Algorithms for the Set Covering Problem