請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52555
標題: | 偏好順序均為完整排列時之熱門配對集合研究 Popular Sets of Matching for Instances with Uniform Permutations of Preferences |
作者: | Chieh-Yu Chen 陳婕妤 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 配對,熱門配對,單側喜好排序列表,二分圖,排列, matchings,popular matchings,one-sided preference lists,bipartite graphs,permutation, |
出版年 : | 2015 |
學位: | 碩士 |
摘要: | 熱門配對問題與分配資源的現實問題高度相關,
由於其特別關注如何在資源有限的狀況下,同時考慮到配對對象的喜好, 近年來被廣泛的研究。熱門配對問題的定義如下:給定 n 個申請人, m 個工作項目,並給定每個申請人對工作項目的喜好排序, 希望找到一個配對,使得其他任何配對,都不會獲得更多申請人的青睞。 這樣的配對稱之為熱門配對。 但熱門配對未必存在,因此我們定義熱門配對集合如下: 對任何一個在熱門配對集合之外的配對,都能在熱門配對集合中 找到一個對手配對,使得喜歡集合中配對的人數不會少於喜歡集合外配對的人數。 本論文的研究均以如下特定情況為前提:m=n,且每個申請人的喜好排序都相同。 排序不容許申請人將不同的工作項目排於同一喜好順位。 我們定義了標準集合 Rn,並證明當 n 為偶數時, Rn 將會是一個熱門配對集合。 當 n 為奇數時,我們證明:倘若給定的配對 T,其所包含逆配對的數量不少於 (n-1)/2 個時, 標準集合 Rn 中必定會存在著 T 的對手配對。 作為日後研究的基礎,本篇論文亦對標準集合定義了數個輔助函數, 並導出他們的簡單式。此外,一些不同觀點的嘗試與觀察亦收錄在本論文中。 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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52555 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-104-1.pdf 目前未授權公開取用 | 662.21 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。