Return to search

On linear programming relaxations of hypergraph matching. / 關於超圖的線性規劃鬆弛 / Guan yu chao tu de xian xing gui hua song chi

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

Identiferoai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_326868
Date January 2009
ContributorsChan, Yuk Hei., Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering.
Source SetsThe Chinese University of Hong Kong
LanguageEnglish, Chinese
Detected LanguageEnglish
TypeText, bibliography
Formatprint, iii, 51 leaves : ill. ; 30 cm.
RightsUse of this resource is governed by the terms and conditions of the Creative Commons “Attribution-NonCommercial-NoDerivatives 4.0 International” License (http://creativecommons.org/licenses/by-nc-nd/4.0/)

Page generated in 0.0021 seconds