請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53184
標題: | 實現熱門配對的演算法設計及複雜度分析 The Complexity and Algorithmic Results of Realizing a Popular Matching |
作者: | Yen-Wei Wu 吳彥緯 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 熱門配對,熱門配對實現,演算法,複雜度, popular matching,popularity,popular matching realization,min-cost augmentation, |
出版年 : | 2015 |
學位: | 博士 |
摘要: | Popular Matching Problem 近年廣受討論,其定義概述如下:給定一群人、一堆物品、以及每個人對物品的偏好順序,目標是將人與物配對(每人至多配得一物,每物至多配予一人),並要求該配對滿足'熱門'的條件。群體比較兩個配對的標準,係由個體依據自身在兩者中獲配的物品,參考自身對物品的偏好順序,將票投給對己有利的一者,獲較多票數的配對即是群體較能接受的一個。當一個配對M,不論與其他任何配對相比較,總能獲得較多或等同數量的票數,則稱M為一個熱門配對。
考量熱門配對並非總是存在,我們定義了一個實用的問題,名為 Popular Matching Realization Problem:在'允許個體權重有別'的前提下,探討如何犧牲最少的群眾權重,確保剩餘的人和物,存在熱門配對關係。在這篇論文中,我們證明了其NP-hardness性質,且進一步指出一個難以逼近最佳解的界線 (於普遍認定的前提下)。此外提出一個高效率的演算法,能在「人人平等」的特例中,求取最佳解。 另外,這篇論文延伸探討 Min-Cost Augmentation Problem:在'允許物品價格有別'的前提下,探討如何以最少的成本複製一些物品,確保後來的人和物,存在熱門配對關係。對照過往文獻,我們推進了該問題難以逼近最佳解的界線,並提出一個更具效率的演算法,能在「物價均等」特例中,求取最佳解。 In this dissertation, we are concerned with the popular matching realization problem, which is an extension of the popular matching problem. An instance of the popular matching problem consists of a set of applicants A, a set of posts P, and a set of preference lists. According to the preference lists, the goal is to match each applicant with at most one unique post so that the resulting matching is 'popular.' A matching M mapping from A to P is popular if there is no other matching M' such that more applicants prefer M' to M than prefer M to M'. However, such a matching does not always exist. To remedy the issue of the non-existence of a popular matching, a possible manipulation is to neglect some applicants such that there is a popular matching for the remaining applicants and posts. Given that each applicant is appended with a cost for neglecting, the popular matching realization problem asks for a subset of applicants, with minimum sum of costs, whose deletion results in an instance admitting a popular matching. We prove that this problem is NP-hard, and it remains NP-hard to approximate to within a certain factor. For the special case where the costs of all applicants are equal, we show that the problem can be solved in O(sqrt{n}m) time, where n is the number of applicants and posts, and m is total length of the preference lists. Furthermore, we prove that the problem can be solved in O(n+m) time if preference lists are strictly ordered. Another extension of the popular matching problem is also considered in this dissertation. Given that each post is appended with a cost for duplicating, the min-cost augmentation problem asks for a set of posts, with minimum sum of costs, whose joining results in an instance admitting a popular matching. The problem has been shown to be NP-hard. We prove it remains NP-hard to approximate to within a factor, which is a stronger lower bound compared with previous work's results. For the special case where the costs of all posts are equal, we show the problem can be solved in O(sqrt{n}m), and in O(n+m) time if preference lists are strictly ordered. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/53184 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 494.91 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。