Chan, Yuk Hei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 49-51). / Abstract also in Chinese. / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Problem Definition --- p.1 / Chapter 1.1.1 --- Hypergraph Matching --- p.1 / Chapter 1.1.2 --- k-Set Packing --- p.2 / Chapter 1.1.3 --- k-Dimensional Matching --- p.2 / Chapter 1.1.4 --- Related Problems --- p.2 / Chapter 1.2 --- Main Result --- p.5 / Chapter 1.3 --- Overview of the Thesis --- p.6 / Chapter 2 --- Background --- p.8 / Chapter 2.1 --- Matching --- p.8 / Chapter 2.1.1 --- Augmenting Path --- p.8 / Chapter 2.1.2 --- Linear Programming --- p.10 / Chapter 2.1.3 --- Matching in General Graphs --- p.11 / Chapter 2.1.4 --- Approximate Min-max Relation for Hypergraphs --- p.11 / Chapter 2.2 --- Local Search --- p.12 / Chapter 2.2.1 --- Unweighted k-Set Packing --- p.12 / Chapter 2.2.2 --- Weighted k-Set Packing ´ؤ (k- - 1 + ₂ё)-approximation --- p.14 / Chapter 2.2.3 --- Weighted k-Set Packing´ؤ(2(k + l)/3 + ₂ё)-approximation --- p.15 / Chapter 2.2.4 --- Weighted k-Set Packing´ؤ((k + l)/2 + ₂ё)-approximation --- p.16 / Chapter 2.3 --- Iterative Rounding --- p.17 / Chapter 2.3.1 --- Basic Solution --- p.17 / Chapter 2.3.2 --- Bipartite Matching --- p.19 / Chapter 2.3.3 --- Generalized Steiner Network Problem --- p.20 / Chapter 2.3.4 --- Minimum Bounded Degree Spanning Tree --- p.22 / Chapter 2.4 --- Packing Problems --- p.24 / Chapter 2.4.1 --- Projective Plane --- p.26 / Chapter 2.5 --- Local Ratio --- p.28 / Chapter 2.5.1 --- Vertex Cover --- p.28 / Chapter 2.5.2 --- Local Ratio Theorem --- p.29 / Chapter 2.5.3 --- Feedback Vertex Set in Tournaments --- p.29 / Chapter 2.5.4 --- Fractional Local Ratio --- p.31 / Chapter 2.5.5 --- Maximum Weight Independent Set in t-interval Graph --- p.31 / Chapter 3 --- k-Dimensional Matching --- p.33 / Chapter 3.1 --- Integrality Gap of the Standard LP Relaxation --- p.33 / Chapter 3.1.1 --- Approximation Algorithm for Unweighted k-D Matching --- p.34 / Chapter 3.1.2 --- Fractional Colouring --- p.35 / Chapter 3.1.3 --- Produce an Ordering --- p.37 / Chapter 3.2 --- Approximation Algorithm for Weighted k-D Matching --- p.38 / Chapter 4 --- k-Set Packing --- p.40 / Chapter 4.1 --- Integrality Gap of the Standard LP Relaxation --- p.40 / Chapter 4.2 --- Improved LP Relaxation for 3-SP --- p.41 / Concluding Remarks --- p.48 / Bibliography --- p.49