請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46578
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chiu-Yun Chuang | en |
dc.contributor.author | 莊秋芸 | zh_TW |
dc.date.accessioned | 2021-06-15T05:16:40Z | - |
dc.date.available | 2010-07-22 | |
dc.date.copyright | 2010-07-22 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-07-21 | |
dc.identifier.citation | [1] Y. Azar, I. Gamzu, and X. Yin. “Multiple intents re-ranking.” In Proceedings of the
41st Annual ACM Symposium on Theory of Computing, 669–678, 2009. [2] S. Babu, R. Motwani, K. Munagala, I. Nishizawa, and J. Widom. “Adaptive ordering of pipelined stream filters.” In Proceedings of the ACM SIGMOD International Conference on Management of Data, 407–418, 2004. [3] N. Bansal, A. Gupta, R Krishnaswamy. “A Constant Factor Approximation Algorithm for Generalized Min-Sum Set Cover,” ACM-SIAM Symposium on Discrete Algorithms, accepted, 2010. [4] A. Bar-Noy, M. M. Halldorsson, G. Kortsarz, “A Matched Approximation Bound for the Sum of a Greedy Coloring,” Information Processing Letters, 71:135–140, 1999. [5] A. Bar-Noy, H. Shachnai and T. Tamir. “On Chromatic Sums and Distributed Resource Allocation,” Information and Computation, 140(2):183–202, 1998. [6] S. Burer and R. Monteiro. “A projected gradient algorithm for solving the maxcut SDP relaxation,” Optimization Methods and Software, 15:175–200, 2001. [7] C. Chekuri and R. Motwani. “Precedence constrained scheduling to minimize sum of weighted completion times on a single machine.” Discrete Applied Mathematics 98(1999), 29–38, 1999. [8] E. Cohen, A. Fiat, and H. Kaplan. “Efficient sequences of trials.” In Proceedings 14th Annual ACM-SIAM Symposium on Discrete Algorithms, 737–746, 2003. [9] U. Feige. “A threshold of ln n for approximating set cover.” Journal of the ACM, 45(4):634–652, 1998. [10] U. Feige, L. Lovasz, P. Tetali. “Approximating min sum set cover.” In Proceedings of APPROX, 94–107, 2002. [11] U. Feige, L. Lovasz and P. Tetali, “Approximating min sum set cover.” Algorithmica, 40, 219–234, 2004. [12] L.A. Hall, A.S. Schulz, D.B. Shmoys, and J. Wein. “Scheduling to minimize average completion time: off-line and on-line approximation algorithms.” Mathematics of Operations Research, 22(3):513–544, 1997. [13] R. Hassin and A. Levin, “An approximation algorithm for the minimum latency set cover problem.” In Proceedings 13th Annual European Symposium on Algorithms, 726–733, 2005. [14] R.M. Karp, “Reducibility Among Combinatorial Problems”. Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, editors. Plenum Press, New York, 85– 103, 1972. [15] H. Kaplan, E. Kushilevitz, and Y. Mansour. “Learning with attribute costs.” In Proceedings 37th Annual ACM Symposium on Theory of Computing, 356–365, 2005. [16] F. Margot, M. Queyranne, and Y. Wang. “Decompositions, network flows, and a precedence constrained single-machine scheduling problem.” Operations Research, 51(6):981–992, 2003. [17] K. Munagala, S. Babu, R. Motwani, and J. Widom. “The pipelined set cover problem.” In Proceedings 10th International Conference on Database Theory, 838, 2005. [18] R. Niedermeier and P. Rossmanith, “An efficient fixed-parameter algorithm for 3- hitting set.” Journal of Discrete Algorithms, 1(1):89–102, 2003. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/46578 | - |
dc.description.abstract | 給定n個元素以及m個集合,最小總和集合涵蓋問題的輸出所有元素的排序;也就是說,從1到n中的每個時間點i,我們都會挑選一個元素,所有在這個時間點i第一次被涵蓋到的集合之涵蓋時間就是i。這個問題的目標就是要找出一個所有元素的排序使得所有集合的涵蓋時間總和可以達到最小。此問題的貪婪演算法每次都選擇可以涵蓋最多集合的元素,在P≠NP的假設下可以達到最優的近似比4。
在此篇論文中,我們著重在貪婪順序,也就是經由貪婪演算法所得到的順序上,並且希望透過重新調整貪婪順序來降低涵蓋時間總和。重新排序的想法主要來自於截斷程序,截斷程序原本是用來證明最小總和著色問題的近似比4+o(1)的最佳性。我們找到截斷程序以及貪婪順序上的相鄰子順序作調換之間一個巧妙的關連,繼而針對調換之後會使得整個順序的涵蓋時間總和降低的相鄰子順序作分析。最後,我們提供了一個演算法可以在O(mn3)的時間內找出所有可能的相鄰子順序之調換。 | zh_TW |
dc.description.abstract | 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). | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T05:16:40Z (GMT). No. of bitstreams: 1 ntu-99-R97922071-1.pdf: 348646 bytes, checksum: a60874657b9a32e3bb9ad09c57167873 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Related work 3 1.2 Our work 4 2 Preliminaries 6 3 The swappable patterns and the chopping algorithm 13 3.1 Chopping procedure 13 3.2 Variants of the chopping procedure 20 3.3 Inverse chopping procedure 23 3.4 Characteristics of the chopping procedure 25 3.5 A swapping algorithm 28 4 Conclusion 33 4.1 Future Works 34 Reference 35 | |
dc.language.iso | en | |
dc.title | 探討最小總和集合涵蓋問題之貪婪順序調換 | zh_TW |
dc.title | On Swapping the Greedy Ordering of the Min-Sum Set Cover Problem | en |
dc.type | Thesis | |
dc.date.schoolyear | 98-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 黃光璿(Guan-Shieng Huang),徐熊健(Shyong-Jian Shyu) | |
dc.subject.keyword | 最小總和集合涵蓋問題,最小集合涵蓋問題,最小碰集問題,貪婪演算法,截斷程序, | zh_TW |
dc.subject.keyword | min sum set cover problem,set cover problem,hitting set problem,greedy algorithm,chopping procedure, | en |
dc.relation.page | 37 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-07-21 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 340.47 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。