請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/72947
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Wei-Liang Shia | en |
dc.contributor.author | 夏維良 | zh_TW |
dc.date.accessioned | 2021-06-17T07:11:21Z | - |
dc.date.available | 2024-07-25 | |
dc.date.copyright | 2019-07-25 | |
dc.date.issued | 2019 | |
dc.date.submitted | 2019-07-19 | |
dc.identifier.citation | [1] S. Dantas, C. M. De Figueiredo, M. C. Golumbic, S. Klein, and F. Maffray. The
chain graph sandwich problem. Annals of Operations Research, 188(1):133–139,2011. [2] P. G. Drange, M. S. Dregi, D. Lokshtanov, and B. D. Sullivan. On the threshold of intractability. In Algorithms-ESA 2015, pages 411–423. 2015. [3] T. Feder, H. Mannila, and E. Terzi. Approximating the minimum chain completion problem. Information Processing Letters, 109(17):980–985, 2009. [4] F. V. Fomin and Y. Villanger. Subexponential parameterized algorithm for minimum fill-in. SIAM Journal on Computing, 42(6):2197–2216, 2013. [5] M. C. Golumbic, H. Kaplan, and R. Shamir. Graph sandwich problems. Journal of Algorithms, 19(3):449–473, 1995. [6] J. Guo. Problem kernels for NP-complete edge deletion problems: split and related graphs. pages 915–926, 2007. [7] Y. Jiao, R. Ravi, and W. Gatterbauer. Algorithms for automatic ranking of participants and tasks in an anonymized contest. Theoretical Computer Science, 2018. [8] M. Kumar, S. Mishra, N. S. Devi, and S. Saurabh. Approximation algorithms for minimum chain vertex deletion. In International Workshop on Algorithms and Computation, pages 21–32, 2011. [9] J. M. Lewis and M. Yannakakis. The node-deletion problem for hereditary properties is np-complete. Journal of Computer and System Sciences, 20:219–230, 1980. [10] A. Natanzon, R. Shamir, and R. Sharan. Complexity classification of some edge modification problems. Discrete Applied Mathematics, 113(1):109–128, 2001. [11] M. Yannakakis. Computing the minimum fill-in is np-complete. SIAM Journal on Algebraic Discrete Methods, 2(1):77–79, 1981. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/72947 | - |
dc.description.abstract | 本論文主要介紹了幾個關於鏈圖修改的問題。在我們探討的問題中會有兩個集合,一個是參加者的集合、另一個則是本次競賽的問題集合。若參賽者答對某個問題,則我們在代表該參賽者的點與代表該問題的點之間加上一條邊。因此,我們可以藉由連接到參賽者點的邊數來區分參賽者實力的強弱。在理想的狀態下,實力強的參賽者答對的題目會是實力弱者答對題目的母集合。同樣的,答對較簡單的問題的參賽者所形成的集合應該是答對較難問題的參賽者的母集合。但是在現實情況,實力強的參賽者可能因為粗心而答錯較簡單的題目,實力弱者可能因為運氣好而猜對較難的題目。而在論文中,我們假設某些問題是沒有鑑別度的,或是某些參賽者的答題情況不具有參考價值。因此,我們的目標是刪除雙分圖中最少的點數,使得此雙分圖變為有序的鏈圖。另一方面,若競賽中允許組隊,我們也提出了一個演算法來估計個隊伍最接近真實實力的排名。最後,假設各參賽者可以在各題中獲取部份分數,在本文中也提供了一個多項式時間的演算法來獲取最接近此參賽者的各提估計分數。 | zh_TW |
dc.description.abstract | We introduce some variants of Chain Editing problem. In our version of
Chain Editing, we are given a set of participants and a set of questions. If a participant answer a question correctly, we add a edge between the participant and the question. Therefore we can distinguish the participants’ ability to solve questions by the degrees of nodes. These nodes stand for the participants. In an ideal world, a stronger participant answers correctly a superset of questions that a weaker participant answers correctly. Similarly, a easier question should be answered correctly by a superset of participants who answers a more difficult question correctly. In reality, it may happen that a stronger have given a wrong answer for a easier question. We assume that some questions are not suitable for the contest. Therefore our goal is to find a perfect nesting of the participant-question relations by deleting a minimum number of questions. In addition, we introduce a variant of the Chain Editing problem for the situation that participants can forms teams for the ranking. Finally, we design an algorithm to get the nearest ideal list of points of a participant when participants can get partial points from each questions. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T07:11:21Z (GMT). No. of bitstreams: 1 ntu-108-R05922075-1.pdf: 696252 bytes, checksum: 9b74bcab8f1409f0327855a4462ea204 (MD5) Previous issue date: 2019 | en |
dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii Abstract iii 1 Introduction 1 1.1 Introduction 1 1.2 Definitions 2 1.3 Related Work 5 2 The Variants of Constrained Chain Problem 7 2.1 The Constrained Chain Vertices Deletion Problem 7 2.1.1 Formulation 7 2.1.2 Complexity 8 2.1.3 An O(n2 22k kk)-time Algorithm for k-near Orderings 8 2.2 The k-union Constrained Chain Editing Problem 9 2.2.1 An O(k2 n2)-time Algorithm 10 3 One Dimension Non-decreasing Sequence With Least Editing 13 3.1 Introduction 13 3.2 Formulation of Problem 13 3.3 Some features of optimal solution 14 3.4 O(n2)-time Algorithm 15 3.4.1 The Recursive Equation 15 3.4.2 Running Time 16 4 Conclusion 17 Bibliography 18 | |
dc.language.iso | en | |
dc.title | 自動排名演算法的改良及延伸 | zh_TW |
dc.title | The Improvements and Extensions of Automatic Ranking Algorithms | en |
dc.type | Thesis | |
dc.date.schoolyear | 107-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王弘倫(Hung-Lung Wang),吳彥緯(Yen-Wei Wu) | |
dc.subject.keyword | 自動排名,鏈圖,非遞減數列, | zh_TW |
dc.subject.keyword | Auto Ranking,chain graph,non-decreasing sequence, | en |
dc.relation.page | 19 | |
dc.identifier.doi | 10.6342/NTU201801286 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2019-07-19 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-108-1.pdf 目前未授權公開取用 | 679.93 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。