Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46578
Title: | 探討最小總和集合涵蓋問題之貪婪順序調換 On Swapping the Greedy Ordering of the Min-Sum Set Cover Problem |
Authors: | Chiu-Yun Chuang 莊秋芸 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 最小總和集合涵蓋問題,最小集合涵蓋問題,最小碰集問題,貪婪演算法,截斷程序, min sum set cover problem,set cover problem,hitting set problem,greedy algorithm,chopping procedure, |
Publication Year : | 2010 |
Degree: | 碩士 |
Abstract: | 給定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 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-99-1.pdf Restricted Access | 340.47 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.