請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51414完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂 | |
| dc.contributor.author | PO-TING LIN | en |
| dc.contributor.author | 林柏廷 | zh_TW |
| dc.date.accessioned | 2021-06-15T13:33:24Z | - |
| dc.date.available | 2018-03-08 | |
| dc.date.copyright | 2016-03-08 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-02-01 | |
| dc.identifier.citation | [1] H.J. Bandelt, Networks with Condorcet solutions, Eur. J. Oper. Res. 20 (1985), pp.
314–326. [2] S. Barberà and C. Beviá, Self-selection consistent functions, J. Econom. Theory 105 (2002), pp. 263–277. [3] S. Barberà and C. Beviá, Locating public facilities by majority: Stability, Consistency and group formation, Games Econ. Behav 56 (2006), pp. 185–200. [4] R.E. Burkard, et al., The obnoxious center problem on a tree, Technical Report 128, Karl Franzens Universitaet Graz and Technische Universitaet Graz, Graz, Austria, 1998. [5] L. Chen, et al., Condorcet winners for public goods, Ann. Oper. Res. 137 (2005), pp. 229–242. [6] N. Christofides and P. Viola, The optimum location of multi-centres on a graph, Oper. Res. Quart. 22 (1971), pp. 145–154. [7] S.L. Hakimi, Optimum locations of switching centres and the absolute centres and medians of a graph, Oper. Res. 12 (1964), pp. 450–459. [8] Hajduková, J. Condorcet winner configurations of linear networks. Optimization, 59, (2010), pp. 461–475. [9] P. Hansen and M. Labbé, Algorithms for voting and competitive location on a network, Trans. Sci. 22 (1988), pp. 278–288. [10] P. Hansen and J.F. Thisse, Outcomes of voting and planning: Condorcet, Weber and Rawls locations, J. Pub. Econom. 16 (1981), pp. 1–15. [11] M. Labbé, Outcomes of voting and planning in single facility location problems, Eur. J Oper. Res. 20 (1985), pp. 299–313. [12] F.E. Maranzana, On the location of supply points to minimize transportation costs, Oper. Res. Quart. 15 (1964), pp. 261–270. [13] A. Tamir, Obnoxious facility location on graphs, SIAM J. Discrete Math. 4 (1991), pp. 550–567. [14] Wu, Y.-W., et al., Computing plurality points and Condorcet points in Euclidean space. In: Proceedings of the International Symposium on Algorithms and Computation, (2013), pp. 688–698. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/51414 | - |
| dc.description.abstract | In this thesis, we study the problem of locating k facilities under major voting criterion when all the voters are distributed along a real line. An optimal
solution to this problem is called a Condorcet winner configuration. Given a placement of k facilities, there exists a fast algorithm to verify whether it is an optimal solution or not [8]. We have found a missing in this algorithm and filled the missing. According to this algorithm and our newly research results, we propose an algorithm for finding an optimal solution. If k is a fixed value, then our algorithm runs in linear time. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T13:33:24Z (GMT). No. of bitstreams: 1 ntu-105-R02922067-1.pdf: 634488 bytes, checksum: 3790fa36264495a8ec41d66eba8f7f13 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 口試委員會審定書 i
誌謝 ii 中文摘要 iii Abstract iv Contents v List of Figures vii 1 Introduction 1 2 Preliminaries 3 2.1 Basic Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Necessary Conditions for Condorcet Winner . . . . . . . . . . . . . . . . 4 2.3 A Sufficient Condition for Condorcet Winner . . . . . . . . . . . . . . . 8 2.4 A Fast Verifying Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Finding Condorcet winner when k ≥ 2 19 3.1 Some Notations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.2 Some Other Necessary Conditions . . . . . . . . . . . . . . . . . . . . . 21 3.3 Proper Similar Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.4 The Maximal Configuration of a Proper Similar Set . . . . . . . . . . . . 35 3.5 An Algorithm for Finding a Condorcet Winner . . . . . . . . . . . . . . 39 4 Concluding Remarks 43 Bibliography 44 | |
| dc.language.iso | en | |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 演算法 | zh_TW |
| dc.subject | 最佳化 | zh_TW |
| dc.subject | 演算法 | zh_TW |
| dc.subject | 多數決 | zh_TW |
| dc.subject | 多數決 | zh_TW |
| dc.subject | 設施設置問題 | zh_TW |
| dc.subject | 設施設置問題 | zh_TW |
| dc.subject | facility location problem | en |
| dc.subject | algorithms | en |
| dc.subject | optimization | en |
| dc.subject | majority voting | en |
| dc.subject | facility location problem | en |
| dc.subject | algorithms | en |
| dc.subject | optimization | en |
| dc.subject | majority voting | en |
| dc.title | 尋找直線上的多數決組合 | zh_TW |
| dc.title | Finding Condorcet Winner Configurations on a Real Line | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 王弘倫,朱安強 | |
| dc.subject.keyword | 設施設置問題,多數決,最佳化,演算法, | zh_TW |
| dc.subject.keyword | facility location problem,majority voting,optimization,algorithms, | en |
| dc.relation.page | 45 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-02-01 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-105-1.pdf 未授權公開取用 | 619.62 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。