Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/50082Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | Wei-Cheng Lin | en |
| dc.contributor.author | 林蔚城 | zh_TW |
| dc.date.accessioned | 2021-06-15T12:29:17Z | - |
| dc.date.available | 2017-08-24 | |
| dc.date.copyright | 2016-08-24 | |
| dc.date.issued | 2016 | |
| dc.date.submitted | 2016-08-05 | |
| dc.identifier.citation | [1] D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM Journal on Computing, 37(4):1030–1045, 2007.
[2] S. Arora. Polynomial time approximation schemes for euclidean tsp and other geometric problems. In Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on, pages 2–11. IEEE, 1996. [3] S. Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM), 45(5):753–782, 1998. [4] H.-J. Bandelt. Networks with condorcet solutions. European Journal of Operational Research, 20(3):314–326, 1985. [5] A. Bauer, W. Domschke, and E. Pesch. Competitive location on a network. European Journal of Operational Research, 66(3):372–391, 1993. [6] M. Bern and P. Plassmann. The steiner problem with edge lengths 1 and 2. Information Processing Letters, 32(4):171–176, 1989. [7] P. Biró, R. W. Irving, and D. F. Manlove. Popular matchings in the marriage and roommates problems. In Algorithms and Complexity, pages 97–108. Springer, 2010. [8] V. Chepoi and F. F. Dragan. Condorcet and median points of simple rectilinear polygons. Location Science, 4(1):21–35, 1996. [9] A. Darmann. Popular spanning trees. International Journal of Foundations of Computer Science, 24(05):655–677, 2013. [10] R. Durier. Continuous location theory under majority rule. Mathematics of Operations Research, 14(2):258–274, 1989. [11] M. Furer and B. Raghavachari. Approximating the minimum-degree steiner tree to within one of optimal. Journal of Algorithms, 17(3):409–423, 1994. [12] G. Galbiati, F. Maffioli, and A. Morzenti. A short note on the approximability of the maximum leaves spanning tree problem. Information Processing Letters, 52(1):45–49, 1994. [13] D. Gale and L. S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962. [14] P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioral Science, 20(3):166–173, 1975. [15] M. R. Garey and D. S. Johnson. Computers and intractability, volume 29. wh freeman New York, 2002. [16] N. Garg. A 3-approximation for the minimum tree spanning k vertices. In focs, page 302. IEEE, 1996. [17] S. L. Hakimi. On locating new facilities in a competitive environment. European Journal of Operational Research, 12(1):29–35, 1983. [18] M. M. Halldórsson, K. Iwano, N. Katoh, and T. Tokuyama. Finding subsets maximizing minimum structures. 1995. [19] P. Hansen and M. Labbé. Algorithms for voting and competitive location on a network. Transportation Science, 22(4):278–288, 1988. [20] P. Hansen and J.-F. Thisse. Outcomes of voting and planning: Condorcet, weber and rawls locations. Journal of Public Economics, 16(1):1–15, 1981. [21] P. Hansen, J.-F. Thisse, and R. Wendell. Equivalence of solutions to network location problems. Mathematics of Operations Research, 11(4):672–678, 1986. [22] P. Hansen, J.-F. Thisse, R. E. Wendell, et al. Equilibrium analysis for voting and competitive location problems. 1990. [23] P. Hansen and M. Zheng. Shortest shortest path trees of a network. Discrete applied mathematics, 65(1):275–284, 1996. [24] R. Hassin and A. Tamir. On the minimum diameter spanning tree problem. Information processing letters, 53(2):109–111, 1995. [25] C.-C. Huang and T. Kavitha. Near-popular matchings in the roommates problem. SIAM Journal on Discrete Mathematics, 27(1):43–62, 2013. [26] C.-C. Huang and T. Kavitha. Popular matchings in the stable marriage problem. Information and Computation, 222:180–194, 2013. [27] M. Karpinski and A. Zelikovsky. New approximation algorithms for the steiner tree problems. Journal of Combinatorial Optimization, 1(1):47–65, 1997. [28] T. Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52–71, 2014. [29] T. Kavitha, M. Nasre, and P. Nimbhorkar. Popularity at minimum cost. Journal of Combinatorial Optimization, 27(3):574–596, 2014. [30] D. Kress and E. Pesch. Sequential competitive location on networks. European Journal of Operational Research, 217(3):483–499, 2012. [31] M. Labbe. Outcomes of voting and planning in single facility location problems. European Journal of Operational Research, 20(3):299–313, 1985. [32] W.-Y. Lin, Y.-W. Wu, H.-L. Wang, and K.-M. Chao. Forming plurality at minimum cost. In WALCOM: Algorithms and Computation, pages 77–88. Springer, 2015. [33] H.-I. Lu and R. Ravi. The power of local optimization: Approximation algorithms for maximum-leaf spanning tree. In Proceedings of the Annual Allerton Conference on Communication Control and Computing, volume 30, pages 533–533. UNIVERSITY OF ILLINOIS, 1992. [34] D. F. Manlove and C. T. Sng. Popular matchings in the capacitated house allocation problem. In Algorithms–ESA 2006, pages 492–503. Springer, 2006. [35] R. M. McCutchen. The least-unpopularity-factor and least-unpopularity-margin criteria for matching problems with one-sided preferences. In LATIN 2008: Theoretical Informatics, pages 593–604. Springer, 2008. [36] R. D. McKelvey and R. E. Wendell. Voting equilibria in multidimensional choice spaces. Mathematics of operations research, 1(2):144–158, 1976. [37] J. Mestre. Weighted popular matchings. In Encyclopedia of Algorithms, pages 1023–1024. Springer, 2008. [38] K. Paluch. Popular and clan-popular b-matchings. Theoretical Computer Science, 544:3–13, 2014. [39] D. Peleg and E. Reshef. Deterministic polylog approximation for minimum communication spanning trees. Springer, 1998. [40] J. Plesník. The complexity of designing a network with minimum diameter. Networks, 11(1):77–85, 1981. [41] C. M. C. Rodrıguez and J. A. M. Pérez. Relaxation of the condorcet and simpson conditions in voting location. European Journal of Operational Research, 145(3):673–683, 2003. [42] C. M. C. Rodríguez and J. A. M. Pérez. Multiple voting location problems. European Journal of Operational Research, 191(2):437–453, 2008. [43] P. J. Slater. Maximin facility location. Journal of National Bureau of Standards B, 79:107–115, 1975. [44] C. T. Sng and D. F. Manlove. Popular matchings in the weighted capacitated house allocation problem. Journal of Discrete Algorithms, 8(2):102–116, 2010. [45] A. Van Zuylen, F. Schalekamp, and D. P. Williamson. Popular ranking. Discrete Applied Mathematics, 165:312–316, 2014. [46] R. Wendell and R. McKelvey. New perspectives in competitive location theory. European Journal of Operational Research, 6(2):174–182, 1981. [47] B. Y. Wu, K.-M. Chao, and C. Y. Tang. Approximation algorithms for some optimum communication spanning tree problems. In ISAAC, volume 98, pages 407–416. Springer, 1998. [48] Y.-W. Wu, W.-Y. Lin, H.-L. Wang, and K.-M. Chao. Computing plurality points and condorcet points in euclidean space. In Algorithms and Computation, pages 688–698. Springer, 2013. [49] Y.-W. Wu, W.-Y. Lin, H.-L. Wang, and K.-M. 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/50082 | - |
| dc.description.abstract | 生成樹問題向來是離散數學與演算法領域中經典的最佳化問題。常應用於現代網路模型及協定之建構，探討如何在最小成本情況下使得各節點之間具連通的功能。而本論文所提出的生成樹，希望從相關傳統問題尋常切入的兩個方向（最小化最大以及最小化總和）外，發展出另一套與投票理論相遇之模型。我們將問題的定義回歸到每個節點自身的需求上。這些需求可能是從自己走到樹中最遠點的距離，也可能是經過樹中每個點的距離總和，或是在樹中與自己相鄰的點數等。我們根據一些初步觀察到的性質，提出在某些情況下有效率的算法，探討如何尋找一棵儘可能滿足大眾偏好的生成樹。 | zh_TW |
| dc.description.abstract | Given an undirected connected graph G = (V, E) we consider the prob-lem of finding a spanning tree of G which preferred by the majority. We called it popular spanning trees problem (PST) and Condorcet spanning trees prob-lem (CST). In this thesis we mainly focus on when voter’s preference criteria is eccentricity on trees. On cycles, we show that finding a PST or verifying if a PST exists can be done in O(|V |2) time. On unit distance graph, we show that finding a PST or verifying if a PST exists can be done in O(|E|3) time, and for the special case where the center is unique, the shortest-path tree from it is a popular spanning tree. On general graphs, when absolute 1-center and Plural point coincide, the shortest-path tree from it is a popular spanning tree. Similarly, when absolute 1-center and Condorcet point coincide, the shortest-path tree from it is a Condorcet spanning tree. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T12:29:17Z (GMT). No. of bitstreams: 1 ntu-105-R03922092-1.pdf: 915624 bytes, checksum: 17067cbff2379b3183367221bb850275 (MD5) Previous issue date: 2016 | en |
| dc.description.tableofcontents | 1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 An Overview of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3.1 Optimization of Spanning Trees in Networks Design . . . . . . . 3 1.3.2 Popularity on Matching . . . . . . . . . . . . . . . . . . . . . . . 4 1.3.3 Popularity on Facility Location . . . . . . . . . . . . . . . . . . 6 2 Formulation of problems 9 2.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Voting Location Problems . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.1 The Condorcet Set . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.2.2 The Plural Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The Popular Spanning Trees Problem . . . . . . . . . . . . . . . . . . . 12 3 The Popular Spanning Trees Problem on Cycle 15 3.1 The Unit Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Observations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.2.1 The First Approach: Largest Edge . . . . . . . . . . . . . . . . . 16 3.2.2 The Second Approach: Balanced Center . . . . . . . . . . . . . . 17 3.3 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.4 An O(n2) – time Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 21 4 The Popular Spanning Trees Problem on Unit Distance Graphs 23 4.1 The Grid Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.2 An O(m3)–time Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 26 5 The Popular Spanning Trees Problem on General Graphs 27 5.1 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.2 Relation to Plural Points . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6 Conclusion 31 6.1 Concluding Remark . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 6.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 6.2.1 The Complexity of PST and CST on General Graph . . . . . . . 32 6.2.2 The Existence of PST and CST . . . . . . . . . . . . . . . . . . 32 6.2.3 The Case when Preference Criterion is Based on Total Distance . 33 6.2.4 The Case when Preference Criterion is Based on Betweenness . . 33 Bibliography 35 | |
| dc.language.iso | en | |
| dc.subject | 投票理論 | zh_TW |
| dc.subject | 生成樹 | zh_TW |
| dc.subject | spanning trees | en |
| dc.subject | voting theory | en |
| dc.title | 大眾化生成樹問題 | zh_TW |
| dc.title | On the Popular Spanning Tree Problem | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 104-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 朱安強(An-Chiang Chu),王弘倫(Hung-Lung Wang) | |
| dc.subject.keyword | 生成樹,投票理論, | zh_TW |
| dc.subject.keyword | spanning trees,voting theory, | en |
| dc.relation.page | 39 | |
| dc.identifier.doi | 10.6342/NTU201601989 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2016-08-07 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| Appears in Collections: | 資訊工程學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-105-1.pdf Restricted Access | 894.16 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.