請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10590完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李德財(Der-Tsai Lee) | |
| dc.contributor.author | Han-Lin Chen | en |
| dc.contributor.author | 陳翰霖 | zh_TW |
| dc.date.accessioned | 2021-05-20T21:41:51Z | - |
| dc.date.available | 2010-08-18 | |
| dc.date.available | 2021-05-20T21:41:51Z | - |
| dc.date.copyright | 2010-08-18 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-08-12 | |
| dc.identifier.citation | [1] J. Alber, H. L. Bodlaender, H. Fernau, T. Kloks, and R. Niedermeier. Fixed parameter
algorithms for dominating set and related problems on planar graphs. Algorithmica, 33(4):461–493, 2002. [2] Jochen Alber, Michael R. Fellows, and Rolf Niedermeier. Polynomial-time data reduction for dominating set. J. ACM, 51(3):363–384, 2004. [3] Brenda S. Baker. Approximation algorithms for np-complete problems on planar graphs. J. ACM, 41(1):153–180, 1994. [4] Judit Bar-Ilan, Guy Kortsarz, and David Peleg. Generalized submodular cover problems and applications. Theor. Comput. Sci., 250(1-2):179–200, 2001. [5] H. L. Bodlaender and A. M. C. A. Koster. Combinatorial optimization on graphs of bounded treewidth. The Computer Journal, 51(3), 2008. [6] Julia Chuzhoy. Covering problems with hard capacities. SIAM J. Comput., 36(2):498–515, 2006. [7] V’aclav Chv’atal. A greedy heuristic for the set-covering problem. Mathematics of Operations Research, 4(3):233–235, 1979. [8] Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated Domination and Covering: A Parameterized Perspective, volume 5018 of Lecture Notes in Computer Science, pages 78–90. Springer Berlin/Heidelberg, 2008. [9] Uriel Feige. A threshold of ln n for approximating set cover. J. ACM, 45(4):634–652, 1998. [10] Fedor V. Fomin and Dimitrios M. Thilikos. Dominating sets in planar graphs: Branch-width and exponential speed-up. SIAM J. Comput., 36(2):281–309, 2006. [11] Sudipto Guha, Refael Hassin, Samir Khuller, and Einat Or. Capacitated vertex covering. J. Algorithms, 48(1):257–270, 2003. [12] Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Michael A. Henning. Domination in graphs applied to electric power networks. SIAM J. Discret. Math., 15(4):519–529, 2002. [13] Teresa W. Haynes, Stephen Hedetniemi, and Peter Slater. Fundamentals of Domination in Graphs (Pure and Applied Mathematics). Marcel Dekker, 1998. [14] D.S. Hochbaum. Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing, 11(3):555–556, 1982. [15] David S. Johnson. Approximation algorithms for combinatorial problems. In STOC ’73: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, pages 38–49, New York, NY, USA, 1973. ACM. [16] Mong-Jen Kao, Chung-Shou Liao, and D. T. Lee. Capacitated domination problem. Algorithmica, 2009. [17] Ton Kloks. Treewidth. Computations and Approximations, volume 842 of Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 1994. [18] Chung-Shou Liao and Der-Tsai Lee. Power Domination Problem in Graphs, volume 3595 of Lecture Notes in Computer Science, pages 818–828. Springer Berlin / Heidelberg, 2005. [19] L’aszlo Lov’asz. On the ratio of optimal integral and fractional covers, 1975. [20] Fred S. Roberts. Graph Theory and Its Applications to Problems of Society. 1978. [21] P.-J. Wan, K. M. Alzoubi, and O. Frieder. A simple heuristic for minimum connected dominating set in graphs. International Journal of Foundations of Computer Science, 14(2):323–333, 2003. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10590 | - |
| dc.description.abstract | 我們考慮容量支配集問題。此問題模型化了一般的服務-需求問題
並且是傳統的支配集問題的一個一般化。在這個問題裡，給定一圖並 在各個點上附有三個參數：價格、容量與需求。我們將要尋找一個最 低價格的配置並滿足需求與容量上的限制。我們在不同的需求配置模 型上提供了多項式時間的近似演算法，此演算法也逼近了傳統的支配 集問題的成果。與已知的前人的結果結合起來，已經從兩個方面逼近 了傳統支配集問題的成果。 | zh_TW |
| dc.description.abstract | We consider the Capacitated Domination problem, which models a service requirement assignment scenario and is also a generalization of the well known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service.
In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models for this problem on general graphs, which also establishes the corresponding approximating results to the well-known approximations of the traditional Dominating Set problem. Together with previously known results, this closes the problem of generally approximating the optimal solution. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-20T21:41:51Z (GMT). No. of bitstreams: 1 ntu-99-R97922104-1.pdf: 570592 bytes, checksum: 6a623e666e97a271cd8e765aed57a738 (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | 中文摘要i
Abstract iii 1 Introduction 1 2 Preliminary 5 2.1 Traditional Domination Problem 5 2.2 Capacitated Domination Problem 7 3 Weighted Unsplittable Demand 11 3.1 The Definition of Efficiency 12 3.2 The Algorithm for Capacitated Domination Problem with Unsplittable Model 13 3.3 Analysis 14 4 Weighted Splittable Demand 17 4.1 The Difference of Demand Assignment between Unsplittable Model and Splittable Model 17 4.2 Definition of Efficiency 18 4.3 The Algorithm for Capacitated Domination Problem with Splittable Model 19 4.4 Analysis 21 5 Unweighted Splittable Demand 27 5.1 The Preprocessing on Problem Instance 27 5.2 The Algorithm for Capacitated Domination Problem with Unweighted Splittable Model 29 5.3 Analysis 30 6 Concluding Remarks 31 7 Appendix 33 Bibliography 35 | |
| dc.language.iso | en | |
| dc.title | 有容量的支配集問題的近似演算法 | zh_TW |
| dc.title | Approximation Algorithms for Capacitated Domination Problem | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 林清池(Ching-Chi Lin),陳健輝(Gen-Huey Chen),張鎮華(Gerard J. Chang) | |
| dc.subject.keyword | 支配集問題,近似演算法, | zh_TW |
| dc.subject.keyword | dominating Set,approximation algorithm, | en |
| dc.relation.page | 37 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2010-08-12 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-99-1.pdf | 557.22 kB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。