令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