電機資訊學院: 資訊工程學研究所指導教授: 趙坤茂吳彥緯Wu, Yen-WeiYen-WeiWu2017-03-032018-07-052017-03-032018-07-052015http://ntur.lib.ntu.edu.tw//handle/246246/275579Popular 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.506784 bytesapplication/pdf論文公開時間: 2015/8/7論文使用權限: 同意有償授權(權利金給回饋本人)熱門配對熱門配對實現演算法複雜度popular matchingpopularitypopular matching realizationmin-cost augmentationthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/275579/1/ntu-104-D98922013-1.pdf