我們研究與圖的擴張值相關的問題。圖的擴張值反映了一個圖的連通程度。很多不同的應用問題都可以轉換成在圖中找一個不擴張的點集，而這亦跟近似理論中的唯一遊戲猜想(unique games conjecture) 有密切的關係。故此，圖的擴張值在應用和理論上均有研究動機。 / 我們介紹有關圖的擴張值的新發現。這些發現包括設計和分析找不擴張的子集的算法、近似算法的困難結論，以及擴張圖的算法應用： / 我們用更多的特徵值去證明一個Cheeger 不等式的推廣，從而較好地分析譜分割算法(spectral graph partitioning algorithm)。 / 我們分析圖上的隨機漫走來設計一個局部的圖分割算法。此算法跟Cheeger 不等式的保證相合。 / 我們給出圖冪的擴張值的緊下界，並用以得到一個關於找小的不擴張子集的困難結論(hardness result)。 / 我們利用擴張圖來設計一個快而簡單的算法來計算矩陣的秩，新算法顯著地改進了以往的算法。 / We study problems related to graph expansions, which measure how well a graph is connected. Various practical problems can be modelled as finding a small non-expanding subset of vertices, and this is also closely related to the unique games conjecture in the theory of approximation algorithms. Hence our study of graph expansions is both practically and theoretically motivated. / We present our new results about graph expansions. The results include the design and analysis of algorithms for finding non-expanding subsets, hardness of approximation results and algorithmic applications of expanders: / We prove a generalization of Cheeger's inequality using higher eigenvalues, providing a better analysis of the spectral graph partitioning algorithm. / We design a local graph partitioning algorithm using random walks on graph, matching the performance guaranteed by Cheeger's inequality. / We give a tight lower bound for the expansion of graph powers and use it to prove hardness results for small set expansions. / We use expanders to design fast and simple algorithms for computing matrix ranks, significantly improving over previous works. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Kwok, Tsz Chiu. / Thesis (Ph.D.) Chinese University of Hong Kong, 2015. / Includes bibliographical references (leaves 104-109). / Abstracts also in Chinese.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_1077666 |
| Date | January 2015 |
| Contributors | Kwok, Tsz Chiu (author.), Lau, Lap Chi (thesis advisor.), Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering, (degree granting institution.) |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography, text |
| Format | electronic resource, electronic resource, remote, 1 online resource (5 unnumbered leaves, 109 leaves) : illustrations, computer, online resource |
| Rights | Use 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.002 seconds