(3.227.235.183) 您好!臺灣時間:2021/04/14 18:10
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蕭凱倫
研究生(外文):Kai-Lun Hsiao
論文名稱:最小三命中集合問題之新啟發式演算法設計與分析
論文名稱(外文):New Heuristics for the Minimum 3-Hitting Set Problem
指導教授:張貿翔張貿翔引用關係吳邦一
指導教授(外文):Maw-Shang ChangBang Ye Wu
口試委員:張貿翔吳邦一李新林黃耀廷
口試委員(外文):Maw-Shang ChangBang Ye WuSing Ling LeeYao-Ting Huang
口試日期:2013-06-28
學位類別:碩士
校院名稱:國立中正大學
系所名稱:資訊工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2013
畢業學年度:101
語文別:英文
論文頁數:45
中文關鍵詞:啟發式演算法命中集合資料結構超圖
外文關鍵詞:heuristichitting setdata structurehypergraph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:361
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:17
  • 收藏至我的研究室書目清單書目收藏:0
令C 是由有限集合S 的子集合所構成的集合,一個命中集合(hitting set) D 是S 的子集合,使得每個在C 中的集合與D 的交集個數至少是1。令(S,C) 是這個最小d 命中集合問題(minimum d-hitting set problem) 的輸入,並且限制所有在C 中的集合大小最多是d。當d ≥ 2 時, 最小d 命中集合問題(minimum d-hitting set problem) 是一個NP 完全問題(NP-complete)。這篇論文中,我們提出了三個啟發式演算(heuristic algorithms) 解最小三命中集合問題(minimum 3-hitting set problem),並且實作這些啟發式演算法。我們透過實驗的方式,比較這些啟發式演算法找到的解集合大小。除此之外,我們以Wahlström 提出的正確解演算法(exact algorithm) 為基礎,實作了一個解決最小三命中集合問題(minimum 3-hitting set problem) 的正確解演算法。啟發式演算法找到的解集合大小是最佳解大小的上限(upper bound),我們利用啟發式演算法找到的解作為正確解演算法中的初始上限(initial upper bound)。我們根據這個正確演算法的特性,設計一個資料結構可以用來減少程式的執行時間。最後,比較我們所實作的正確解演算法和最佳化軟體IBM ILOG CPLEX Optimizer 在解決最小三命中集合問題(minimum 3-hitting set problem) 的執行時間。

Let C = {C1,C2, . . . ,Cm} be a collection of subsets of a finite set S. A hitting set D is a subset of S such that for i = 1, 2, . . . ,m, |D ∩ Ci| ≥ 1. An instance (S,C) is an input of the Minimum d-Hitting Set problem if |Ci| ≤ d for 1 ≤ i ≤ m. The Minimum d-Hitting Set problem is NP-complete for d ≥ 2. In this thesis, we design three heuristic algorithms for the Minimum 3-Hitting Set (Min 3-hs) problem and implement them. We compare the solutions found by the heuristic algorithms. Moreover, we implement an exact algorithm based on the algorithm given by Wahlstr¨om [25] for the Min 3-hs problem. We take the solutions found by our heuristic algorithms as an initial upper bound in the exact algorithm. We design a data structure to speedup the exact algorithm for the Min 3-hs problem. We compare the running time of the exact algorithm for the Min 3-hs with the commercial optimization software, IBM ILOG CPLEX Optimizer.
1 Introduction
1.1 Motivation
1.2 Previous results
1.3 Applications
1.4 The main results

2 Preliminaries
2.1 Notation
2.2 0/1 Integer linear programming formulations

3 Heuristic algorithms and an exact algorithm
3.1 Heuristic algorithm SelectAll
3.2 Heuristic algorithm SelectMax
3.3 Heuristic algorithm DiscardMin
3.4 A branch-and-reduce algorithm

4 Experiment results
4.1 Data structure
4.2 The test data
4.3 Experiment results

5 Conclusions

[1] F. N. Abu-Khzan, A kernelization algorithm for d-hitting set, Journal of Computer System Science 76 (2010), pp. 524–531.
[2] C. Berge, Hypergraphs, North Holland, 1989.
[3] D. Bryant, M. Fellows, V. Raman, and U. Stege, On the parameterized complexity of MAST and 3-hitting sets, Unpublished manuscript (1988).
[4] J. Chen, I. A. Kanj, and W. Jia, Vertex cover: further observations and furtherimprovements, Journal of Algorithms, 41 (2001), pp. 280–301.
[5] J. Chen, I. A. Kanj, and G. Xia, Improved parameterized upper bounds for vertex cover, Proceedings of MFCS 2006, LNCS 4162, pp. 238–249, 2006.
[6] M.-S. Chang and L.-J. Hung, Moderately exponential time approximation algorithms for the maximum bounded-degree-1 set problem, Proceedings of the 30th Workshop on Combinatorial Mathematics and Computation Theory, pp. 23–30, 2013.
[7] I. Dinur and S. Safra, The importance of being biased, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pp. 33–42, 2002.
[8] I. Dinur, V. Guruswami, S. Khot, and O. Regev, A new multilayered PCP and the hardness of hypergraph vertex cover, SIAM Journal on Computing 34(5) (2005), pp. 1129–1146.
[9] R. G. Downey and M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.
[10] H. Fernau, A top-down approach to search-trees: improved algorithmicsfor 3-hitting set. Algorithmica 57 (2010), pp. 97–118.
[11] L. Brankovic and H. Fernau, Parameterized approximation algorithms for hitting set, Proceedings of WAOA 2011, LNCS 7164, pp. 63–76, 2012.
[12] H. Fernau, Parameterized algorithms for hitting set: the weighted case, Proceedings of the 6th Italian Conference on Algorithms and Complex-ity (CIAC-2006), pp. 332–343, 2006.
[13] U. Feige, A threshold of ln n for approximating set cover, Journal of the ACM 45 (1998), pp. 634–652.
[14] F. V. Fomin, F. Grandoni, and D. Kratsch, Measure and conquer:domination – a case study, Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, LNCS 3580, pp. 191–203, 2005.
[15] M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, New York, 1979.
[16] G. Gallo, G. Longo, S. Pallottino, and S. Nguyen, Directed hypergraphs and applications, Discrete Applied Mathematics 42 (1993), pp. 177–201.
[17] F. Kuhn, P. von Rickenbach, R. Wattenhofer, E. Welzl, and A. Zollinger, Interference in cellular networks: the minimum membership set cover problem, Proceedings of the 11th annual international conference on Computing and Combinatorics, pp. 188–198, 2005.
[18] H. Moser, R. Niedermeier, and M. Sorge, Exact combinatorial algorithms and experiments for finding maximum k-plexes, Journal of Combinatorial Optimization 24 (2012), pp. 347–373.
[19] R. Niedermeier, P. Rossmanith, An efficient fixed-parameter algorithm for 3-hitting set, Journal of Discrete Algorithms 1 (2003), pp. 89–102.
[20] R. Reiter, A theory of diagnosis from first principles, Arti cial Intelligence 32 (1987), pp. 57–95.
[21] D. Ruchkys, S. Song, A parallel approximation hitting set algorithm for gene expression analysis, Proceedings of the 14th Symposium on Computer Architecture and High Performance Computing, pp. 75–81, 2002.
[22] S. B. Seidman and B. L. Foster, A graph-theoretic generalization of the clique concept, The Journal of Mathematical Sociology 6 (1978), pp. 139–154.
[23] S. Skiena, The Algorithm Design Manual, Springe (1998).
[24] M. Wahlstr¨om, Exact algorithms for finding minimum transversalsin rank-3 hypergraphs, Journal of Algorithms 51 (2004), pp. 107–121.
[25] M.Wahlstr¨om, Algorithms, measures and upper bounds for satis ability and related Problems, Ph.D. thesis, Link¨oping Studies in Science and Technology, 2007.
[26] D. Zhou, J. Huang and B. Sch¨olkopf, Beyond pairwise classification and clustering using hypergraphs, MPI Technical Report, No. 143 (2005).
[27] CPLEX Optimizer
http://www-01.ibm.com/software/commerce/optimization/cplexoptimizer/
[28] DIMACS: Maximum clique, graph coloring, and satisfiability, Second DIMACS implementation challenge (1995).
http://dimacs.rutgers.edu/Challenges/
[29] Wikipedia, http://en.wikipedia.org/wiki/CPLEX

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔