https://scholars.lib.ntu.edu.tw/handle/123456789/119410
標題: | 實現熱門配對的演算法設計及複雜度分析 The Complexity and Algorithmic Results of Realizing a Popular Matching |
作者: | 吳彥緯 Wu, Yen-Wei |
關鍵字: | 熱門配對;熱門配對實現;演算法;複雜度;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://ntur.lib.ntu.edu.tw//handle/246246/275579 | Rights: | 論文公開時間: 2015/8/7 論文使用權限: 同意有償授權(權利金給回饋本人) |
顯示於: | 資訊工程學系 |
檔案 | 描述 | 大小 | 格式 | |
---|---|---|---|---|
ntu-104-D98922013-1.pdf | 23.32 kB | Adobe PDF | 檢視/開啟 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。