請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46578
標題: | 探討最小總和集合涵蓋問題之貪婪順序調換 On Swapping the Greedy Ordering of the Min-Sum Set Cover Problem |
作者: | Chiu-Yun Chuang 莊秋芸 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 最小總和集合涵蓋問題,最小集合涵蓋問題,最小碰集問題,貪婪演算法,截斷程序, min sum set cover problem,set cover problem,hitting set problem,greedy algorithm,chopping procedure, |
出版年 : | 2010 |
學位: | 碩士 |
摘要: | 給定n個元素以及m個集合,最小總和集合涵蓋問題的輸出所有元素的排序;也就是說,從1到n中的每個時間點i,我們都會挑選一個元素,所有在這個時間點i第一次被涵蓋到的集合之涵蓋時間就是i。這個問題的目標就是要找出一個所有元素的排序使得所有集合的涵蓋時間總和可以達到最小。此問題的貪婪演算法每次都選擇可以涵蓋最多集合的元素,在P≠NP的假設下可以達到最優的近似比4。
在此篇論文中,我們著重在貪婪順序,也就是經由貪婪演算法所得到的順序上,並且希望透過重新調整貪婪順序來降低涵蓋時間總和。重新排序的想法主要來自於截斷程序,截斷程序原本是用來證明最小總和著色問題的近似比4+o(1)的最佳性。我們找到截斷程序以及貪婪順序上的相鄰子順序作調換之間一個巧妙的關連,繼而針對調換之後會使得整個順序的涵蓋時間總和降低的相鄰子順序作分析。最後,我們提供了一個演算法可以在O(mn3)的時間內找出所有可能的相鄰子順序之調換。 Given a universe of n elements and a collection of m sets, the output of the min sum set cover problem (MSSC) is an ordering of all the elements, namely, in every time step i from 1 to n we pick an element. All the sets covered for the first time at time i have cover time i, and the goal of the MSSC problem is to find an ordering of the elements such that the total cover time of all the sets is minimized. The greedy algorithm that always picks the element which covers the most sets achieves the approximation ratio 4, and it is NP-hard to approximate it within 4 − ϵ. In this thesis, we work on the output of the greedy algorithm, which we call the greedy ordering, and try to rearrange it so that we can lower the total cover time. The idea of the rearrangement comes from the chopping procedure, which has been used to prove that the 4+o(1) ratio of the approximation algorithm for the minimum sum coloring problem is tight. We find a subtle relationship between the chopping procedure and the adjacent swap on the greedy ordering. Then we analyse the patterns of the adjacent suborderings where their swap will help lower the total cover time. Last, we give a swapping algorithm which checks all possible suborderings are swappable or not in time O(mn3). |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46578 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 340.47 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。