請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
dc.contributor.author | Ming-Wei Shao | en |
dc.contributor.author | 邵明偉 | zh_TW |
dc.date.accessioned | 2021-06-16T06:43:51Z | - |
dc.date.available | 2014-08-01 | |
dc.date.copyright | 2014-08-01 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-07-28 | |
dc.identifier.citation | [1] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. E cient algorithms for the weighted
2-center problem in a cactus graph. In Xiaotie Deng and Ding-Zhu Du, editors, Algorithms and Computation, Lecture Notes in Computer Science, pages 693{703. Springer Berlin Heidelberg, 2005. [2] B. Ben-Moshe, B. Bhattacharya, and Q. Shi. An optimal algorithm for the continuous/ discrete weighted 2-center problem in trees. In Proceedings of the 7th Latin American Conference on Theoretical Informatics, pages 166{177, 2006. [3] Y.K. Cheng, L.Y. Kang, and H. Yan. The backup 2-median problem on block graphs. Acta Mathematicae Applicatae Sinica, English Series, pages 309{320, 2014. [4] G.N. Frederickson. Parametric search and locating supply centers in trees. In Frank Dehne, J org-R udiger Sack, and Nicola Santoro, editors, Algorithms and Data Struc- tures, Lecture Notes in Computer Science, pages 299{319. Springer Berlin Heidelberg, 1991. [5] G.N. Frederickson and D.B. Johnson. Finding kth paths and p-centers by generating and searching good data structures. Journal of Algorithms, pages 61{80, 1983. [6] Y. Hong and L. Kang. Backup 2-center on interval graphs. Theoretical Computer Science, pages 25{35, 2012. [7] M. Jeger and O Kariv. Algorithms for nding p-centers on a weighted tree (for relatively small p). Networks, pages 381{389, 1985. [8] O. Kariv and S.L. Hakimi. An algorithm approach to network location problems: part I. the p-centers. SIAM Journal on Applied Mathematics, pages 513{538, 1979. [9] Y.F. Lan, Y.L. Wang, and H. Suzuki. A linear-time algorithm for solving the center problem on weighted cactus graphs. Information Processing Letters, pages 205 { 212, 1999. [10] N. Megiddo. Linear-time algorithms for linear programming in R3 and related problems. SIAM Journal on Computing, pages 759{776, 1983. [11] N. Megiddo and A. Tamir. New results on the complexity of p-center problems. SIAM Journal on Computing, pages 751{758, 1983. [12] N. Megiddo, A. Tamir, E. Zemel, and R. Chandrasekaran. An O(n log2 n) algorithm for the kth longest path in a tree with applications to location problems. SIAM Journal on Computing, pages 328{337, 1981. [13] L.V. Snyder. Facility location under uncertainty: A review. IIE Transactions, pages 537{554, 2006. [14] L.V. Snyder and M.S. Daskin. Reliability models for facility location: The expected failure cost case. Transport Science, pages 400{416, 2005. [15] A. Tamir. Sorting weighted distances with applications to objective function evaluations in single facility location problems. Operations Research Letters, pages 249{257, 2004. [16] H.L. Wang, B.Y. Wu, and K.M. Chao. The backup 2-center and backup 2-median problems on trees. Networks, pages 39{49, 2009. [17] B.Y. Wu and K.M. Chao. Spanning Trees and Optimization Problems. CRC Press, 2004. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/57382 | - |
dc.description.abstract | 本論文引用王教授所提出的基於可靠性的備份雙中心模式,在這模式中,每個設施
皆有壞掉機率。我們假設此二設施不會同時壞掉,在這前提下一旦有一設施壞掉,另 一設施需負責所有服務。在路徑圖上具權重的備份雙中心問題中,我們想在點帶權重 之路徑圖上架設此二設施,使得權重距離期望值最小。假設路徑圖上有n個點,我們 建立了一個時間複雜度為O(n)的演算法。 | zh_TW |
dc.description.abstract | In this thesis, we apply the reliability-based backup 2-center model proposed by Wang, where each facility may fail with a given probability. Once a facility fails, the other has to be responsible for all the services. We assume that two facilities do not fail at the same time. In the weighted backup 2-center problem on paths, we want to locate two
facilities on vertex-weighted paths such that the expected weighted distance is minimized. We construct an O(n)-time algorithm, where n is the number of vertices in the given path. | en |
dc.description.provenance | Made available in DSpace on 2021-06-16T06:43:51Z (GMT). No. of bitstreams: 1 ntu-103-R01922128-1.pdf: 587553 bytes, checksum: 2ddeb0a3accf8e394f4be4b42cc9cb4b (MD5) Previous issue date: 2014 | en |
dc.description.tableofcontents | 1 Introduction 1
2 Problem Denition and Notation 4 3 The Weighted Backup 2-center Problem on paths 7 3.1 Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Properties of Weighted Backup 2-center . . . . . . . . . . . . . . . . . . . . 9 3.3 The First Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Methods for the enhancement . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.5 A Faster Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 4 Conclusion 27 4.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 | |
dc.language.iso | en | |
dc.title | 路徑圖上權重備份雙中心問題 | zh_TW |
dc.title | The Weighted Backup 2-center Problem on Paths | en |
dc.type | Thesis | |
dc.date.schoolyear | 102-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 王弘倫(Hung-Lun Wang),朱安強(An-Chiang Chu) | |
dc.subject.keyword | 圖論,權重距離,備份雙中心,路徑圖,位置問題, | zh_TW |
dc.subject.keyword | graph theory,weighted distance,backup 2-center,path,location problem, | en |
dc.relation.page | 30 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2014-07-28 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf 目前未授權公開取用 | 573.78 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。