請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69909
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Ming-Hsuan Hsieh | en |
dc.contributor.author | 謝名宣 | zh_TW |
dc.date.accessioned | 2021-06-17T03:33:35Z | - |
dc.date.available | 2021-03-02 | |
dc.date.copyright | 2018-03-02 | |
dc.date.issued | 2016 | |
dc.date.submitted | 2018-02-13 | |
dc.identifier.citation | [1] Julien Basch, Leonidas J. Guibas, and Ramkumar G.D. Reporting red-blue intersections between two sets of connected line segments. Algorithms —ESA ’96, pages 302–319, 1996.
[2] Julien Basch, Leonidas J. Guibas, and John Hershberger. Data structures for mobile data. Journal of Algorithms, pages 1–28, 1999. [3] G. S. Brodal and R. Jacob. Dynamic planar convex hull. The 43rd Annual IEEE Symposium on Foundations of Computer Science, page 617–626, 2002. [4] Rainer E. Burkard, Helidon Dollani, Yixun Lin, and Günter Rote. The obnoxious center problem on a tree. SIAM J. Discrete Math, 14:498–509, 2001. [5] Timothy M. Chan. Remarks on k-level algorithms in the plane. Technical report, 1999. [6] Guilgerme D. da Fonseca, Celina M.H. de Figueriredo, and Oaulo C.P. Carvalho. Kinetic hanger. Information Processing Letters, pages 151–157, 2004. [7] T. K. Dey. Improved bounds on planar k-sets and k-levels. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 156–161, 1997. [8] Csoke Meghan E. The facility location problem. All Student Theses, 2015. [9] H. Edelsbrunner and E. Welzl. Constructing belts in twodimensional arrangements with applications. SIAM Journal on Computing, 15(1):271–284, 1986. [10] Sudipo Guha and Samir Khuller. Greedy strikes back: Improved facility location algorithms. Journal of Algorithms, 31:228–248, 1999. [11] Dorrie H. 100 great problems of elementary mathematics: their history and solution. Dover Publications, New York, 1965. [12] S. Har-Peled. Taking a walk in a planar arrangement. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039), pages 100–110, 1999. [13] Antonio J. Lozano, Juan A. Mesa, and Frank Plastria. Finding an euclidean anti-k-centrum location of a set of points. Computers & Operations Research, 37(2):292 – 301, 2010. [14] Nimrod Megiddo and Arie Tamir. On the complexity of locating linear facilities in the plane. Operations Research Letters, pages 194–197, 1982. [15] Nenad Mladenović, Martine Labbé, and Pierre Hansen. Solving the p-center problem with tabu search and variable neighborhood search. Networks, 42(1):48–64, 2003. [16] Arie Tamir. Obnoxious facility location on grapgs. SIAM J. Discrete Math, pages 550–567, 1991. [17] Arie Tamir. The k-centrum multi-facility location problem. Discrete Appl. Math., 109:293–307, 2001. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/69909 | - |
dc.description.abstract | 我們研究在給定的路徑圖上如何找出一個機構的anti-k-centrum 位址。意思是說,路徑圖上每一頂點到此機構的加權距離,取前k 小的值加總要最大。
我們提出了兩種類似的演算法,第一個演算法我們將所想到的方式一步一步執行,其時間複雜度取決於所使用的k-level 演算法。Timothy 提出一隨機演算法求k-level,時間複雜度為O(n log n + nk1/3),由Dey 證明在最壞狀況下k-level 的轉折點個數為m = O(nk1/3),n是路徑圖的頂點個數,k 是一小於n 的常數。 第二個演算法利用了動態優先權序列來求解,時間複雜度為O(T(n; n + m)),其中T(n;m) = O(m (n)), (n) 表示一逆阿克曼函數。 | zh_TW |
dc.description.abstract | In this thesis, we plan to find a facility placed on the edge of a given path, which meets the demand constraints of anti-k-centrum location problem.
We provide two algorithms to solve the problem. The first algorithm uses k-level algorithm helping us, the time complexity of the first algorithm depends on the speed of constructing the k-level. Timothy showed a randomized algorithm constructing the k-level, that runs an expected time O(n log n + nk1/3), n is the number of vertices on the given path, with the bound by Dey showing that the number of turning points on k-level is m = O(nk1/3) in the worst case. The second algorithm uses an abstract data structure call kinetic priority queue. The time complexity is O(T(n,n+m)),which T(n,m) = O(m (n)), and (n) denote the inverse Ackermann function. | en |
dc.description.provenance | Made available in DSpace on 2021-06-17T03:33:35Z (GMT). No. of bitstreams: 1 ntu-105-R02922113-1.pdf: 929165 bytes, checksum: 481b658614804fb7e33a5d1c9a0c8df0 (MD5) Previous issue date: 2016 | en |
dc.description.tableofcontents | 口試委員審定書(i)
摘要(ii) Abstract(iii) 1 Introduction(1) 2 Related Work(4) 2.1 k-level algorithm(4) 2.2 kinetic priority queue(6) 3 The Anti-k-centrum on a path(7) 3.1 Algorithm step by step(8) 3.2 Algorithm using kinetic priority queue(10) 4 Conclusion(14) 4.1 Future work(14) Bibliography(16) | |
dc.language.iso | en | |
dc.title | 路徑圖上anti-k-centrum 選址問題 | zh_TW |
dc.title | The anti-k-centrum location problem on a path | en |
dc.type | Thesis | |
dc.date.schoolyear | 106-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王弘倫,吳彥緯 | |
dc.subject.keyword | 路徑圖,定址問題,演算法,動態優先權序列,加權距離,k-level,anti-k-centrum, | zh_TW |
dc.subject.keyword | path,location problem,k-level,anti-k-centrum,kinetic priority queue,algorithm,weighted distance, | en |
dc.relation.page | 17 | |
dc.identifier.doi | 10.6342/NTU201800472 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2018-02-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-105-1.pdf 目前未授權公開取用 | 907.39 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。