請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52897完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Wei-Yin Lin | en |
| dc.contributor.author | 林蔚茵 | zh_TW |
| dc.date.accessioned | 2021-06-15T16:32:54Z | - |
| dc.date.available | 2015-08-16 | |
| dc.date.copyright | 2015-08-16 | |
| dc.date.issued | 2015 | |
| dc.date.submitted | 2015-08-13 | |
| dc.identifier.citation | Bibliography
[1] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn, “Popular matchings,” SIAM Journal on Computing, Vol. 37(4), pp. 1030–1045, 2007. [2] P. Afshani, “On approximate range counting and depth,” Discrete and Computational Geometry, Vol. 42(1), pp. 3–21, 2009. [3] G. Aloupis, C. Cortes, F. Gomez, M. Soss, and G. T. Toussaint, “Lower bounds for computing statistical depth,” Computational Statistics & Data Analysis, Vol. 40(2), pp. 223–229, 2002. [4] G. Aloupis, S. Langerman, M. Soss, and G. T. Toussaint, “Algorithms for bivariate medians and a Fermat-Torricelli problem for lines,” Computational Geometry, Vol. 26(1), pp. 69–79, 2003. [5] H.-J. Bandelt, “Networks with Condorcet solutions,” European Journal of Operational Research, Vol. 20(3), pp. 314–326, 1985. [6] S. Barberà and C. Bevia, “Locating public facilities by majority: stability, consistency and group formation,” Games and Economic Behavior, Vol. 56(1), pp. 185–200, 2006. [7] J. J. Bartholdi, C. A. Tovey, and M. A. Trick, “How hard is it to control an election?,” Mathematical and Computer Modeling, Vol. 16(8–9), pp. 27–40, 1992. [8] A. Bauer, W. Domschke, and E. Pesch, “Competitive location on a network,” European Journal of Operational Research, Vol. 66(3), pp. 372–391, 1993. [9] C. M. Campos Rodríguez and J. A. Moreno Pérez, “The tolerant Condorcet points,” Studies in Locational Analysis, Vol. 14, pp. 173–190, 2000. [10] C. M. Campos Rodríguez and J. A. Moreno Pérez, “Relaxation of the Condorcet and Simpson conditions in voting location,” European Journal of Operational Research, Vol. 145(3), pp. 673–683, 2003. [11] C. M. Campos Rodríguez and J. A. Moreno Pérez, “Multiple voting location problems,” European Journal of Operational Research, Vol. 191(2), pp. 437–453, 2008. [12] E. Carrizosa, E. Conde, M. Muñoz-Márquez, and J. Puerto, “Simpson points in planar problems with locational constraints. The round-norm case,” Mathematics of Operations Research, Vol. 22(2), pp. 276–290, 1997. [13] E. Carrizosa, E. Conde, M. Muñoz-Márquez, and J. Puerto, “Simpson points in planar problems with locational constraints. The polyhedral gauge case,” Mathematics of Operations Research, Vol. 22(2), pp. 291–300, 1997. [14] T. M. Chan, “An optimal randomized algorithm for maximum Tukey depth,” Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 430–436, 2004. [15] V. Chepoi and F. Dragan, “Condorcet and median points of simple rectilinear polygons,” Location Science, Vol. 4(1–2), pp. 21–35, 1996. [16] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 3rd ed., 2009. [17] O. A. Davis, M. H. DeGroot, and M. J. Hinich, “Social preference orderings and majority rule,” Econometrica, Vol. 40(1), pp. 147–157, 1972. [18] O. A. Davis, M. J. Hinich, and P. C. Ordeshook, “An expository development of a mathematical model of the electoral process,” The American Political Science Review, Vol. 64(2), pp. 426–448, 1970. [19] G. Demange, “Spatial models of collective choice,” In: J.-F. Thisse and H. G. Zoller (eds.), Locational Analysis of Public Facilities, North-Holland, Amsterdam, 1983. [20] A. Downs, An Economic Theory of Democracy, New York: Harper, 1957. [21] Z. Drezner, “Competitive location strategies for two facilities,” Regional Science and Urban Economics, Vol. 12(4), pp. 485–493, 1994. [22] T. Drezner, “Optimal continuous location of a retail facility, facility attractiveness, and market share: An interactive model,” Journal of Retailing, Vol. 70(1), pp. 49–64, 1994. [23] R. Durier, “Continuous location theory under majority rule,” Mathematics of Operations Research, Vol. 14(2), pp. 258–274, 1989. [24] H. A. Eiselt and G. Laporte, “Competitive spatial models” European Journal of Operational Research, Vol. 39(3), pp. 231–242, 1989. [25] H. A. Eiselt, G. Laporte, and J.-F. Thisse, “Competitive location models: A framework and bibliography” Transportation Science, Vol. 27(1), pp. 44–54, 1993. [26] S. Gehlbach, Formal Models of Domestic Politics, New York: Cambridge University Press, 2013. [27] J. Gill, W. Steiger, and A. Wigderson, “Geometric medians,” Discrete Mathematics, Vol. 108(1–3), pp. 37–51, 1992. [28] J. Hajduková, “Condorcet winner configurations of linear networks,” Optimization, Vol. 59(4), pp. 461–475, 2010. [29] P. Hansen and M. Labbé, “Algorithms for voting and competitive location on a network,” Transportation Science, Vol. 22(4), pp. 278–288, 1988. [30] P. Hansen and J.-F. Thisse, “Outcomes of voting and planning : Condorcet, Weber and Rawls locations,” Journal of Public Economics, Vol. 16(1), pp. 1–15, 1981. [31] P. Hansen, J.-F. Thisse, and R. E. Wendell, “Equivalence of solutions to network location problems,” Mathematics of Operations Research, Vol. 11(4), pp. 672–678, 1986. [32] P. Hansen, J.-F. Thisse, and R. E. Wendell, “Equilibrium analysis for voting and competitive location,” In: P. Mirchandani and R. Francis (eds.), Discrete Location Theory, John Wiley and Sons, New York, pp. 479–502, 1990. [33] H. Hotelling, “Stability in competition,” Economic Journal, Vol. 39, pp. 41–57, 1929. [34] G. H. Kramer, “A dynamical model of political equilibrium,” Journal of Economic Theory, Vol. 16, pp. 310–334, 1977. [35] D. Kress and E. Pesch, “Sequential competitive location on networks,” European Journal of Operational Research, Vol. 217(3), pp. 483–499, 2012. [36] M. van Kreveld, J. S. B. Mitchell, P. Rousseeuw, M. Sharir, J. Snoeyink, and B. Speckmann, “Efficient algorithms for maximum regression depth,” Discrete & Computational Geometry, Vol. 39(4), pp. 656–677, 2008. [37] H. W. Kuhn, “On a pair of dual nonlinear programs,” In: J. Abadie (ed.), Nonlinear programming (North-Holland, Amsterdam), pp. 37–54, 1967. [38] M. Labbé, “Outcomes of voting and planning in single facility location problems,” European Journal of Operational Research, Vol. 20(3), pp. 299–313, 1985. [39] M. Labbé, “Location of an obnoxious facility on a network: a voting approach,” Networks, Vol. 20, pp. 197–207, 1990. [40] S. Langerman and W. Steiger, “The complexity of hyperplane depth in the plane,” Discrete & Computational Geometry, Vol. 30(2), pp. 299–309, 2003. [41] W.-Y. Lin, Y.-W. Wu, H.-L. Wang, and K.-M. Chao, “Forming plurality at minimum cost,” Proceedings of the 9th International Workshop on Algorithms and Computation, pp. 77–88, 2015. [42] R. F. Love, J. G. Morris, G. O. Wesolowsky, Facilities location: models and methods, North Holland, NY, 1988. [43] R. D. McKelvey, P. C. Ordeshook, and P. Ungar, “Conditions for voting equilibria in continuous voter distributions,” SIAM Journal on Applied Mathematics, Vol. 39(1), pp. 161–168, 1980. [44] R. D. McKelvey and R. E. Wendell, “Voting equilibria in multidimensional choice spaces,” Mathematics of Operations Research, Vol. 1(2), pp. 144–158 1976. [45] N. Megiddo, “Linear-time algorithms for linear programming inR3 and related problems,” SIAM Journal on Computing, Vol. 12(4), pp. 759–776, 1983. [46] N. Megiddo, “Linear programming in linear time when the dimension is fixed,” Journal of the ACM, Vol. 31(1), pp. 114–127, 1984. [47] K. Miller, S. Ramaswami, P. Rousseeuw, J. A. Sellarès, D. Souvaine, I. Streinu, and A. Struyf, “Efficient computation of location depth contours by methods of computational geometry,” Statistics and Computing, Vol. 13(2), pp. 153–162, 2003. [48] H. Noltemeier, J. Spoerhase, and H.-C. Wirth, “Multiple voting location and single voting location on trees,” European Journal of Operational Research, Vol. 181(2), pp. 654–667, 2007. [49] F. Plastria, “Continuous location problems,” In: Z. Drezner (ed.), Facility Location. A survey of Applications and Methods, Springer, Berlin, pp. 225–262, 1995. [50] C. R. Plott, “A Notion of equilibrium and its possibility under majority rule,” The American Economic Review, Vol. 57(4), pp. 787–806, 1967. [51] P. J. Rousseeuw and A. Struyf, “Computing location depth and regression depth in higher dimensions,” Statistics and Computing, Vol. 8(3), pp. 193–203, 1998. [52] P. B. Simpson, “On defining areas of voter choice: Professor Tullock on stable voting,” Quarterly Journal of Economics, Vol. 83(3), pp. 478–490, 1969. [53] A. Sothers, “On the complexity of matrix multiplication,” PhD thesis, University of Edinburg, 2010. [54] J. J. Sylvester, “A question in the geometry of situation,” Quarterly Journal of Mathematics, Vol. 1, p. 79, 1857. [55] M. Taylor, “Review article: mathematical political theory,” British Journal of Political Science, Vol. 1(3), pp. 339–382, 1971. [56] R. L. Tobin and T. L. Friesz, “Spatial competition facility location models: Definition, formulation and solution approach,” Annals of Operations Research, Vol. 6(3), pp. 47–74, 1986. [57] J. Tukey, “Mathematics and the picturing of data,” Proceedings of the International Congress of Mathematicians, Vol. 2, pp. 523–531, 1975. [58] R. V. Vohra, “Distance weighted voting and a single facility location problem,” European Journal of Operational Research, Vol. 41(3), pp. 314–320, 1989. [59] R. E. Wendell and R. D. McKelvey, “New perspectives in competitive location theory,” European Journal of Operational Research, Vol. 6(2), pp. 174–182, 1981. [60] R. E. Wendell and S. J. Thorson, “Some generalizations of social decisions under majority rule,” Econometrica, Vol. 42(5), pp. 893–912, 1974. [61] G. O. Wesolowsky, “The Weber problem: history and perspectives,” Location Science, Vol. 1, pp. 5–23, 1993. [62] Y.-W. Wu, W.-Y. Lin, H.-L. Wang, and K.-M. Chao, “Computing plurality points and Condorcet points in Euclidean space,” Proceedings of the 24th International Symposium on Algorithms and Computation, pp. 688–698, 2013. [63] A. van Zuylen, F. Schalekamp, and D. P. Williamson, “Popular ranking,” Discrete Applied Mathematics, Vol. 165(11), pp. 312–316, 2014. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/52897 | - |
| dc.description.abstract | The purpose of this dissertation is to study the properties of plurality points and design an efficient algorithm to find them. Given a multiset of $n$ points equipped with the $ell_2$-norm, a emph{plurality point} is a location which is closer to at least as many given points as any other location. This spatial equilibrium formed by voting has been studied for decades in both the field of economy and location theory. For any $d$-dimensional space where $d$ is fixed, we present an $O(n^{d-1} log n)$-time algorithm to compute the point. However, the plurality point may not exist if the given points are not collinear. In order to find an alternative solution, some related problem extensions are also investigated in this dissertation. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T16:32:54Z (GMT). No. of bitstreams: 1 ntu-104-F97922079-1.pdf: 815601 bytes, checksum: 8c09c07588ea7d9e35bd70ce13df19cb (MD5) Previous issue date: 2015 | en |
| dc.description.tableofcontents | 口試委員會審定書i
致謝ii 中文摘要iv Abstract v Contents vi List of Figures viii List of Tables x 1 Introduction 1 1.1 Preliminaries 2 1.2 Condorcet Points 3 1.3 Historical Review 4 2 Plurality Points in Two-dimensional Space 8 2.1 The Collinear Case 8 2.2 Properties 9 2.3 Tukey Depth 17 2.4 An O(n log n)-time Algorithm 20 3 Plurality Points in High-dimensional Space 23 3.1 Properties 23 3.2 An O(n^{d−1} log n)-time Algorithm 27 4 The Minimum-cost Plurality Problem 29 4.1 Problem Definition and Notation 29 4.2 Properties 31 4.3 NP-hardness 32 4.4 The Case where Voters are Equally Weighted 35 5 Concluding Remarks 45 5.1 Summary 45 5.2 Directions for Future Research 46 | |
| dc.language.iso | en | |
| dc.subject | 演算法 | zh_TW |
| dc.subject | 歐式空間 | zh_TW |
| dc.subject | 多數決策點 | zh_TW |
| dc.subject | plurality point | en |
| dc.subject | algorithm | en |
| dc.subject | Euclidean space | en |
| dc.title | 在歐式空間中尋找多數決策點 | zh_TW |
| dc.title | Finding Plurality Points in Euclidean Space | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 103-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 陳健輝(Gen-Huey Chen),歐陽彥正(Yen-Jen Oyang),呂育道(Yuh-Dauh Lyuu),劉邦鋒(Pangfeng Liu) | |
| dc.subject.keyword | 演算法,歐式空間,多數決策點, | zh_TW |
| dc.subject.keyword | algorithm,Euclidean space,plurality point, | en |
| dc.relation.page | 54 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2015-08-13 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-104-1.pdf 未授權公開取用 | 796.49 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。