請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52555
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Chieh-Yu Chen | en |
dc.contributor.author | 陳婕妤 | zh_TW |
dc.date.accessioned | 2021-06-15T16:18:26Z | - |
dc.date.available | 2015-10-17 | |
dc.date.copyright | 2015-08-20 | |
dc.date.issued | 2015 | |
dc.date.submitted | 2015-08-17 | |
dc.identifier.citation | [1] Peter Gärdenfors. Match making: assignments based on bilateral preferences. Behavioral Science, 20(3):166–173, 1975.
[2] David J Abraham,Robert W Irving,Telikepalli Kavitha, and Kurt Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030–1045, 2007. [3] David J Abraham, Katarína Cechlárová, David F Manlove, and Kurt Mehlhorn. Pareto optimality in house allocation problems. In Algorithms and Computation, pages 1163–1175. Springer, 2005. [4] Atila Abdulkadiroğlu and Tayfun Sönmez. Random serial dictatorship and the core from random endowments in house allocation problems. Econometrica, pages 689–701, 1998. [5] Alvin E Roth and Andrew Postlewaite. Weak versus strong domination in a market with indivisible goods. Journal of Mathematical Economics, 4(2):131–137, 1977. [6] Robert W Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, and Katarzyna Paluch. Rank-maximal matchings. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 68–75. Society for Industrial and Applied Mathematics, 2004. [7] Telikepalli Kavitha, Julián Mestre, and Meghana Nasre. Popular mixed matchings. Theoretical Computer Science, 412(24):2679–2690, 2011. [8] Telikepalli Kavitha and Meghana Nasre. Popular matchings with variable item copies. Theoretical Computer Science, 412(12):1263–1274, 2011. [9] Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pages 216–226. ACM, 1978. [10] Yen-Wei Wu, Wei-Yin Lin, Hung-Lung Wang, and Kun-Mao Chao. The generalized popular condensation problem. In Algorithms and Computation, pages 606–617. Springer, 2014. [11] Richard Matthew McCutchen.The least-unpopularity-factor and least-unpopularity- margin criteria for matching problems with one-sided preferences. In LATIN 2008: Theoretical Informatics, pages 593–604. Springer, 2008. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52555 | - |
dc.description.abstract | 熱門配對問題與分配資源的現實問題高度相關,
由於其特別關注如何在資源有限的狀況下,同時考慮到配對對象的喜好, 近年來被廣泛的研究。熱門配對問題的定義如下:給定 n 個申請人, m 個工作項目,並給定每個申請人對工作項目的喜好排序, 希望找到一個配對,使得其他任何配對,都不會獲得更多申請人的青睞。 這樣的配對稱之為熱門配對。 但熱門配對未必存在,因此我們定義熱門配對集合如下: 對任何一個在熱門配對集合之外的配對,都能在熱門配對集合中 找到一個對手配對,使得喜歡集合中配對的人數不會少於喜歡集合外配對的人數。 本論文的研究均以如下特定情況為前提:m=n,且每個申請人的喜好排序都相同。 排序不容許申請人將不同的工作項目排於同一喜好順位。 我們定義了標準集合 Rn,並證明當 n 為偶數時, Rn 將會是一個熱門配對集合。 當 n 為奇數時,我們證明:倘若給定的配對 T,其所包含逆配對的數量不少於 (n-1)/2 個時, 標準集合 Rn 中必定會存在著 T 的對手配對。 作為日後研究的基礎,本篇論文亦對標準集合定義了數個輔助函數, 並導出他們的簡單式。此外,一些不同觀點的嘗試與觀察亦收錄在本論文中。 | zh_TW |
dc.description.abstract | Popular matching problems have been explored in recent years, as they are highly related to
realistic problems that allocate limited resources and taking requesters' preference in concern. An instance of a popular matching problem consists of n applicants, m posts, and n preference lists which rank the posts for each applicant. A Popular matching M is the one that no other matching is preferred by more applicants when comparing with M. Since popular matching might not exist, we define the popular set S, which gathers a set of matching, such that for any given matching T, there exists a rival matching S in S that S is preferred by at least as many applicants as T. Our inspection focuses on a specialized case that m=n, and all preference lists are the same, each of which ranks all posts and contains no tie. We also compose the {em regular set} Rn, and prove when n is even, Rn is a popular set. For odd n, we show that if a given matching T contains no less than (n-1)/2 negative matches, there is a rival matching against T in the regular set. For further study on the case that n is odd, we also derive auxiliary functions for the regular set, and raise some observations from several different points of view. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T16:18:26Z (GMT). No. of bitstreams: 1 ntu-104-R94922054-1.pdf: 678100 bytes, checksum: 8aede1862027a72a4ea0a26f0c710694 (MD5) Previous issue date: 2015 | en |
dc.description.tableofcontents | 口試委員審定書 i
致謝 ii 中文摘要 iii Abstract iv Contents v List of Tables vii 1 Introduction 1 1.1 Popular Matching Problem ......................... 1 1.2 Related Works................................ 2 1.3 Our Result.................................. 2 1.4 Thesis Organization............................. 3 2 Preliminaries 4 2.1 The Popular Matching Set Problem..................... 4 2.2 Restriction: Uniform Permutations of Preferences . . . . . . . . . . . . . 5 2.3 Regular Matching Set............................ 5 2.4 Notation................................... 6 3 Regular Set with an Even Number of Applicants 7 4 Regular Set with an Odd Number of Applicants 10 4.1 Extending T and Rn to the Even Case ................... 10 4.2 Method1:Inspecting φ and E....................... 11 4.2.1 Investigation of E(Rn,T) ..................... 11 4.2.2 Inspection of φ(Rn,T)....................... 14 4.2.3 A Subcase of Odd n Where Regular Matching Set Contains a Rival Matching of T ......................... 15 4.2.4 Inspecting the Remaining Cases .................. 16 4.3 Method 2: Finding a Rival Matching from the Even Cases .................. 17 5 Concluding Remarks and Future Work 22 5.1 Concluding Remarks ............................ 22 5.2 Future Work................................. 23 Bibliography 24 | |
dc.language.iso | en | |
dc.title | 偏好順序均為完整排列時之熱門配對集合研究 | zh_TW |
dc.title | Popular Sets of Matching for Instances with Uniform Permutations of Preferences | en |
dc.type | Thesis | |
dc.date.schoolyear | 103-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 黃耀廷(Yao-Ting Huang),王弘倫(Hung-Lung Wang) | |
dc.subject.keyword | 配對,熱門配對,單側喜好排序列表,二分圖,排列, | zh_TW |
dc.subject.keyword | matchings,popular matchings,one-sided preference lists,bipartite graphs,permutation, | en |
dc.relation.page | 25 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2015-08-17 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 662.21 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。