請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51411
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Kuan-Wei Chen | en |
dc.contributor.author | 陳冠維 | zh_TW |
dc.date.accessioned | 2021-06-15T13:33:18Z | - |
dc.date.available | 2022-03-12 | |
dc.date.copyright | 2019-03-12 | |
dc.date.issued | 2016 | |
dc.date.submitted | 2016-02-01 | |
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] Chieh-Yu Chen. Popular sets of matching for instance with uniform permutation of preferences. 國立臺灣大學電資學院資訊工程研究所碩士論文, 2015. [9] McCutchen and Richard Matthew. The least-unpopularity-factor and leastunpopularity-margin criteria for matching problems with one-sided preferences. In LATIN 2008: Theoretical Informatics, pages 593–604. Springer, 2008. [10] Telikepalli Kavitha and Meghana Nasre. Popular matchings with variable item copies. Theoretical Computer Science, 412(12):1263–1274, 2011. [11] C. A. Tovey J. J. Bartholdi and M. A. Trick. How hard is it to control an election? Mathmatical and Computer Modeling, 16(8/9):27–40, 1992. [12] 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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51411 | - |
dc.description.abstract | 熱門配對問題是一個長年來備受關注的議題,其主要在考慮如何在有限的資源情況下加上人人平等的假設前提,將資源做有效率的分配。熱門配對問題定義如下: 給定m個申請人,n 個工作項目,以及每位申請人對工作項目之喜好順序,欲找到一個申請人與工作項目之間的配對,且保證沒有任何其他配對較此配對受到更多申請人的青睞,並稱此配對為“熱門配對”。然而,熱門配對並不總是存在,因此有許多替代的準則仍被持續討論當中, 例如: Pareto optimal, rank-maximal 等等。甚至,對於配對之“不熱門性” 亦有人提出想法。本篇論文採用熱門配對集合之定義並在以下特殊情況下做討論: m 與n 相等,每位申請人之喜好順序皆一致並且沒有一位申請人對兩個工作項目之喜好程度相同。我們另外將此問題與有限對稱群之觀念結合,提出兩者間的對應關係,並在標準集合的基礎下另外定義了廣義標準集合以及關鍵長度函數CL(n),並證明對所有的整數n,指標為CL(n)之廣義標準集合為一熱門配對集合。最後,對於小於17 的整數,我們利用電腦精確的求出其關建長度。對於較大的整數,我們利用抽樣的方法估計之,並觀察期變化趨勢。 | zh_TW |
dc.description.abstract | The popular matching problem is widely discussed in recent year. It’s mainly attributed to solve the problem about limited resources distribution in an efficient way. An instance of the popular matching problem consists of n
applicants ,m posts and n preference lists which rank the posts for each applicants. The output is a matching M between applicants and posts. In addition, no other matching is preferred by more applicants when comparing with M. We call such matching M a popular matching. Since popular matching may not exist, several interesting alternative criteria have been proposed such as pareto optimal and rank-maximal. The “unopularities” of a matching were also discussed. We focus on one of the alternative criteria : popular matching set problem . A popular matching set S gathering a set of matchings assures that for any given matching M, there exist a rival matching in S. Besides, three assumptions are considered in this work : (1) m equals n. (2) all preference lists are the same. (3) Each preference list ranks all posts and contains no tie. We also combine finite symmetric group with this problem and propose a mapping between matchings and group. In addition, we also define the generalized regular set and critical length function CL(n). Finally, we prove that for all n, generalized regular set with index CL(n) is a popular matching set. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T13:33:18Z (GMT). No. of bitstreams: 1 ntu-105-R02922116-1.pdf: 335874 bytes, checksum: 1a296b1ab4ff05f7cc264b8521057593 (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Popular Matching Problem . . . . 1 1.2 Related Work . . . . . . . . . . 2 1.3 Our Results . . . . . . . . . . 3 1.4 Thesis Organization . . . . . . 3 2 Preliminaries 5 2.1 Popular Matching Set Problem . . . . . 5 2.1.1 Definition . . . . . . . . . . . . . 5 2.1.2 Restriction . . . . . . . . . . . . 6 2.2 Finite Symmetric Group . . . . . . . . 6 2.3 Notation . . . . . . . . . . . . . . . 7 3 Finite Symmetric Group Mapping 9 3.1 Nature Function Mapping . . . . . . . . 9 3.2 Matching Sign of Permutation Function . . . . . . 10 4 Solving Popular Matching Set Problem with Finite Symmetric Group 14 4.1 Critical Length Function . . . . . . . 14 4.2 Generalized Regular Matching . . . . . 16 4.3 Estimate of Critical Length . . . . . . 17 5 Conclusion and Future Work 19 5.1 Conclusion . . . . . . . . . . 19 5.2 Future Work . . . . . . . . . 19 Bibliography 21 | |
dc.language.iso | en | |
dc.title | 結合有限對稱群觀點之熱門配對集合研究 | zh_TW |
dc.title | Popular Sets of Matching Combined with Finite Symmetric Group | en |
dc.type | Thesis | |
dc.date.schoolyear | 104-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王弘倫(Hung-Lung Wang),朱安強(An-Chiang Chu) | |
dc.subject.keyword | 配對,熱門配對,單側喜好排序列表,二分圖,有限對稱群, | zh_TW |
dc.subject.keyword | matchings,popular matchings,one-sided preference lists,bipartite graphs,permutation,finite symmetric group, | en |
dc.relation.page | 22 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2016-02-02 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 328 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。