請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65696完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 李德財(D.T. Lee) | |
| dc.contributor.author | Mong-Jen Kao | en |
| dc.contributor.author | 高孟駿 | zh_TW |
| dc.date.accessioned | 2021-06-16T23:59:43Z | - |
| dc.date.available | 2012-07-19 | |
| dc.date.copyright | 2012-07-19 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-07-16 | |
| dc.identifier.citation | [1] I. Abraham, Y. Bartal, T.-H. H. Chan, K. D. Dhamdhere, A. Gupta, J. Kleinberg, O. Neiman, and A. Slivkins, Metric em
beddings with relaxed guarantees, in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS '05, Washington,DC, USA, 2005, IEEE Computer Society, pp. 83-100. [2] I. Abraham, Y. Bartal, and O. Neiman, On embedding of finite metric spaces into hilbert space. manuscript, 2005. [3] I. Abraham, Y. Bartal, and O. Neiman, Embedding metrics into ultra-metrics and graphs into spanning trees with constant average distortion, in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '07, Philadelphia, PA, USA, 2007, Society for ndustrial and Applied Mathematics, pp. 502-511. [4] I. Abraham, Y. Bartal, and O. Neimany, Advances in metric embedding theory, in Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, STOC '06, New York, NY, USA, 2006, ACM, pp. 271-286. [5] A. V. Aho and J. E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1st ed., 1974. [6] 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 (2002), pp. 461-493. [7] J. Alber, M. R. Fellows, and R. Niedermeier, Polynomial-time data reduction for dominating set, Journal of ACM, 51 (2004), pp. 363-384. [8] N. Alon, R. Karp, D. Peleg, and D. West, A graph-theoretic game and its application to the k-server problem, SIAM Journal on Computing, 24(1995), pp. 78-100. [9] N. Alon, R. Yuster, and U. Zwick, Color-coding, Journal of ACM, 42(1995), pp. 844-856. [10] B. S. Baker, Approximation algorithms for NP-complete problems on planar graphs, Journal of ACM, 41 (1994), pp. 153-180. [11] V. B alint, The non-approximability of bicriteria network design problems, Journal of Discrete Algorithms, 1 (2003), pp. 339-355. [12] Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, in Proceedings of the 37th Annual Symposium on Foundations of Computer Science, FOCS '96, Washington, DC, USA, 1996, IEEE Computer Society, pp. 184-. [13] Y. Bartal, On approximating arbitrary metrices by tree metrics, in Proceedings of the thirtieth annual ACM symposium on Theory of computing, STOC'98, New York, NY, USA, 1998, ACM, pp. 161-168. [14] Y. Bartal, Graph decomposition lemmas and their role in metric embedding methods, in European Symposium on Algorithms, ESA'04, 2004, pp. 89-97. [15] Y. Bartal, N. Linial, M. Mendel, and A. Naor, On metric ramsey-type phenomena, in Proceedings of the thirty- fifth annual ACM symposium on Theory of computing, STOC '03, New York, NY, USA, 2003, ACM, pp. 463-472. [16] H. L. Bodlaender, A linear time algorithm for nding tree-decompositions of small treewidth, in Proceedings of the twenty- fth annual ACM symposium on Theory of computing, STOC '93, New York, NY, USA, 1993, ACM, pp. 226-234. [17] P. Bose, On embedding an outer-planar graph in a point set, Computional Geometry: Theory and Applications, 23 (2002), pp. 303-312. [18] M. Cesati, Compendium of parameterized problems. 2006. [19] R. Chandrasekaran, Minimal ratio spanning trees, Networks, 7 (1977), pp. 335-342. [20] M. Charikar, C. Chekuri, A. Goel, S. Guha, and S. Plotkin, Approximating a nite metric by a small number of tree metrics, in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, FOCS '98, Washington, DC, USA, 1998, IEEE Computer Society, pp. 379-. [21] A. Chinchuluun and P. Pardalos, A survey of recent developments in multiobjective optimization, Annals of Operations Research, 154 (2007), pp. 29-50. [22] F. A. Chudak and D. P. Williamson, Improved approximation algorithms for capacitated facility location problems, Mathematical Programming, 102 (2005), pp. 207-222. [23] K.-M. Chung and H.-I. Lu, An optimal algorithm for the maximum-density segment problem, SIAM Journal on Computing, 34 (2005), pp. 373-387. [24] J. Chuzhoy, Covering problems with hard capacities, SIAM Journal on Computing, 36 (2006), pp. 498-515. [25] S. A. Cook, The complexity of theorem-proving procedures, in Proceedings of the third annual ACM symposium on Theory of computing, STOC '71, New York, NY, USA, 1971, ACM, pp. 151-158. [26] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2nd ed., 2001. [27] E. D. Demaine, F. V. Fomin, M. Hajiaghayi, and D. M. Thi likos, Subexponential parameterized algorithms on bounded-genus graphs and h-minor-free graphs, Journal of ACM, 52 (2005), pp. 866-893. [28] R. G. Downey and M. Fellows, Parameterized Complexity, Springer, 1999. [29] R. G. Downey and M. R. Fellows, Fixed-parameter tractability and completeness II: On completeness for W[1], Theoretical Computer Science, 141 (1995), pp. 109-131. [30] S. Dreyfus and R. Wagner, The Steiner problem in graphs, Networks, 1 (1971), pp. 195-207. [31] M. Elkin, Y. Emek, D. A. Spielman, and S.-H. Teng, Lower-stretch spanning trees, in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, STOC '05, New York, NY, USA, 2005, ACM, pp. 494-503. [32] D. Eppstein, Subgraph isomorphism in planar graphs and related problems, in Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA '95, Philadelphia, PA, USA, 1995, Society for Industrial and Applied Mathematics, pp. 632-640. [33] M. Erwig, The graph Voronoi diagram with applications, Networks, 36 (2000), pp. 156-163. [34] J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, in Proceedings of the thirty- fifth annual ACM symposium on Theory of computing, STOC '03, New York, NY, USA, 2003, ACM, pp. 448-455. [35] U. Feige, A threshold of ln n for approximating set cover, Journal of ACM, 45 (1998), pp. 634-652. [36] J. Flum and M. Grohe, Parameterized Complexity Theory, Texts in Theoretical Computer Science. An EATCS Series, Springer, 1 ed., Mar. 2006. [37] F. V. Fomin and D. M. Thilikos, Dominating sets in planar graphs: Branch-width and exponential speed-up, SIAM Journal on Computing, 36 (2006), pp. 281-309. [38] S. Fortune, A sweepline algorithm for Voronoi diagrams, Algorithmica, 2 (1987), pp. 153-174. [39] H. N. Gabow, Data structures for weighted matching and nearest common ancestors with linking, in Proceedings of the rst annual ACM-SIAM symposium on Discrete algorithms, SODA '90, Philadelphia, PA, USA, 1990, Society for Industrial and Applied Mathematics, pp. 434-443. [40] R. Gandhi, E. Halperin, S. Khuller, G. Kortsarz, and A. Srinivasan, An improved approximation algorithm for vertex cover with hard capacities, Journal of Computer and System Sciences, 72 (2006), pp. 16-33. [41] R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan, Dependent rounding in bipartite graphs, in Proceedings of the 43rd Symposium on Foundations of Computer Science, FOCS '02, Washington, DC, USA, 2002, IEEE Computer Society, pp. 323-332. [42] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979. [43] M. H. Goldwasser, M.-Y. Kao, and H.-I. Lu, Linear-time algorithms for computing maximum-density sequence segments with bioinformatics applications, Journal of Computer and System Sciences, 70 (2005), pp. 128-144. [44] J. Gross and J. Yellen, Graph theory and its applications, CRC Press, Inc., Boca Raton, FL, USA, 1999. [45] S. Guha, R. Hassin, S. Khuller, and E. Or, Capacitated vertex covering, Journal of Algorithms, 48 (2003), pp. 257-270. [46] J. Guo and R. Niedermeier, Linear problem kernels for NP-hard problems on planar graphs, in International Colloquium on Automata, Languages and Programming, ICALP'07, 2007, pp. 375-386. [47] T. W. Haynes, S. Hedetniemi, and P. Slater, Fundamentals of Domination in Graphs (Pure and Applied Mathematics), Marcel Dekker, 1998. [48] T. W. Haynes, S. M. Hedetniemi, S. T. Hedetniemi, and M. A. Henning, Domination in graphs applied to electric power networks, SIAM Journal on Discrete Mathematics, 15 (2002), pp. 519-529. [49] J.-M. Ho, Optimal trees in network design, PhD thesis, Evanston, IL, USA, 1989. UMI Order No: GAX90-01807. [50] J.-M. Ho, D. T. Lee, C.-H. Chang, and C. K. Wong, Minimum diameter spanning trees and related problems, SIAM Journal on Computing, 20 (1991), pp. 987-997. [51] D. Hochbaum, Approximation algorithms for the set covering and vertex cover problems, SIAM Journal on Computing, 11 (1982), pp. 555-556. [52] J. Hopcroft and R. Tarjan, E cient planarity testing, Journal of ACM, 21 (1974), pp. 549-568. [53] S.-Y. Hsieh and C.-S. Cheng, Finding a maximum-density path in a tree under the weight and length constraints, Information Processing Letters, 105 (2008), pp. 202-205. [54] S.-Y. Hsieh and T.-Y. Chou, Algorithms and Computation, vol. 3827 of LNCS, Springer Berlin / Heidelberg, 2005, ch. Finding a Weight-Constrained Maximum-Density Subtree in a Tree, pp. 944-953. [55] F. Hurtado, R. Klein, E. Langetepe, and V. Sacrist an, The weighted farthest color Voronoi diagram on trees and graphs, Computational Geometry, 27 (2004), pp. 13-26. [56] R. B. Inman, A denaturation map of the lambda phage dna molecule determined by electron microscopy, Journal of Molecular Biology, 18 (1966), pp. 464-476. [57] K. Jain and V. V. Vazirani, Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation, Journal of ACM, 48 (2001), pp. 274-296. [58] D. S. Johnson, Approximation algorithms for combinatorial problems, in the 5th annual ACM symposium on Theory of computing, New York, NY, USA, 1973, ACM, pp. 38-49. [59] D. S. Johnson, J. K. Lenstra, and A. H. G. R. Kan, The complexity of the network design problem, Networks, 8 (1978), pp. 279-285. [60] M.-J. Kao and H.-L. Chen, Approximation algorithms for the capacitated domination problem, in International Frontiers of Algorithmics Workshop, FAW'10, Berlin, Heidelberg, 2010, Springer-Verlag, pp. 185-196. [61] M.-J. Kao and D. T. Lee, Capacitated domination: Constant factor approximations for planar graphs, in International Symposium on Algorithms and Computation, ISAAC'11, 2011, pp. 494-503. [62] M.-J. Kao, C.-S. Liao, and D. T. Lee, Capacitated domination problem, Algorithmica, 60 (2011), pp. 274-300. 10.1007/s00453-009-9336-x. [63] D. Karger, R. Motwani, and G. Ramkumar, On approximat- ing the longest path in a graph, Algorithmica, 18 (1997), pp. 82-98. 10.1007/BF02523689. [64] D. Kirkpatrick, Optimal search in planar subdivisions, SIAM Journal on Computing, 12 (1983), pp. 28-35. [65] J. Kleinberg, A. Slivkins, and T. Wexler, Triangulation and embedding using small sets of beacons, Journal of ACM, 56 (2009), pp. 32:1-32:37. [66] T. Kloks, Treewidth, Computations and Approximations, vol. 842 of Lecture Notes in Computer Science, Springer, 1994. [67] K. Kuratowski, Sur le Probleme des Courbes Gauches en Topologie, Fundamenta Mathematicae, 15 (1930), pp. 271-283. [68] H. C. Lau, T. H. Ngo, and B. N. Nguyen, Finding a length-constrained maximum-sum or maximum-density subtree and its application to logistics, Discrete Optimization, 3 (2006), pp. 385-391. [69] D. T. Lee, T.-C. Lin, and H.-I. Lu, Fast algorithms for the density nding problem, Algorithmica, 53 (2009), pp. 298-313. [70] C.-S. Liao and G. J. Chang, k-tuple domination in graphs, Information Processing Letters, 87 (2003), pp. 45-50. [71] C.-S. Liao and D.-T. Lee, Power domination problem in graphs, in International Computing and Combinatorics Conference, COCOON'05, 2005, pp. 818-828. [72] Y.-L. Lin, T. Jiang, and K.-M. Chao, E cient algorithms for locating the length-constrained heaviest segments with applications to biomolecular sequence analysis, Journal of Computer and System Sciences, 65 (2002), pp. 570-586. [73] H.-F. Liu and K.-M. Chao, Algorithms for nding the weight-constrained k longest paths in a tree and the length-constrained k maximum-sum segments of a sequence, Theoretical Computer Science, 407 (2008), pp. 349-358. [74] D. Lokshtanov, New Methods in Parameterized Algorithms and Complexity, PhD thesis, University of Bergen Norway, 2009. [75] G. Macaya, J.-P. Thiery, and G. Bernardi, An approach to the organization of eukaryotic genomes at a macromolecular level, Journal of Molecular Biology, 108 (1976), pp. 237-254. [76] M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt, Bicriteria network design problems,, Journal of Algorithms, 28 (1998), pp. 142-171. [77] E. M. McCreight, Priority search trees, SIAM Journal on Computing, 14 (1985), pp. 257-276. [78] G. Narasimhan and M. Smid, Geometric Spanner Networks, Cambridge University Press, New York, NY, USA, 2007. [79] R. Niedermeier, Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications), Oxford University Press, USA, Mar. 2006. [80] M. H. Overmars and J. van Leeuwen, Maintenance of con gurations in the plane, Journal of Computer and System Sciences, 23 (1981), pp. 166-204. [81] M. P al, E. Tardos, and T. Wexler, Facility location with nonuniform hard capacities, in Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, FOCS '01, Washington, DC, USA, 2001, IEEE Computer Society, pp. 329-. [82] C. M. Papadimitriou, Computational complexity, Addison-Wesley, Reading, Massachusetts, 1994. [83] Y. Rabinovich, On average distortion of embedding metrics into the line and into l1, in Proceedings of the thirty- fifth annual ACM symposium on Theory of computing, STOC '03, New York, NY, USA, 2003, ACM, pp. 456-462. [84] Y. Rabinovich and R. Raz, Lower bounds on the distortion of embedding nite metric spaces in graphs, Discrete and Computational Geometry, 19 (1996). [85] R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz, and S. S. Ravi, Spanning trees|short or small, SIAM Journal on Discrete Mathematics, 9 (1996), pp. 178-200. [86] F. S. Roberts, Graph Theory and Its Applications to Problems of Society, 1978. [87] N. Robertson and P. D. Seymour, Graph minors. iii. planar tree-width, Journal of Combinatorial Theory, Series B, 36 (1984), pp. 49-64. [88] G. Robins and A. Zelikovsky, Improved steiner tree approximation in graphs, in Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, SODA '00, Philadelphia, PA, USA, 2000, Society for Industrial and Applied Mathematics, pp. 770-779. [89] P. Schuurman and G. Woeginger, Approximation schemes - a tutorial, 2011. preliminary version of a chapter in the book Lectures on Scheduling. [90] R. Seidel, Constrained Delaunay triangulations and Voronoi diagrams with obstacles, Tech. Report 260, IIG-TU Graz, Austria, 1988. [91] D. Y. Seo, On the complexity of bicriteria spanning tree problems for a set of points in the plane, PhD thesis, Evanston, IL, USA, 1999. AAI9953371. [92] A. Shapira, R. Yuster, and U. Zwick, All-pairs bottleneck paths in vertex weighted graphs, in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, SODA '07, Philadelphia, PA, USA, 2007, Society for Industrial and Applied Mathematics, pp. 978-985. [93] D. B. Shmoys, E. Tardos, and K. Aardal, Approximation algorithms for facility location problems (extended abstract), in Proceedings of the twentyninth annual ACM symposium on Theory of computing, STOC '97, New York, NY, USA, 1997, ACM, pp. 265-274. [94] M. Smid, Spanning trees with o(1) average stretch factor. manuscript, 2009. [95] R. J. Vanderbei, Linear Programming: Foundations and Extensions, Department of operations and research and nancial engineering, Princeton university, 2001. [96] V. Vassilevska, R. Williams, and R. Yuster, All-pairs bottleneck paths for general graphs in truly sub-cubic time, in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, STOC '07, New York, NY, USA, 2007, ACM, pp. 585-589. [97] V. V. Vazirani, Approximation Algorithms, Springer, Mar. 2004. [98] 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 (2003), pp. 323-333. [99] D. B. West, Introduction to Graph Theory (2nd Edition), Prentice Hall, Aug. 2000. [100] R. Wong, Worst-case analysis of network design problem heuristics, SIAM Journal on Algebraic and Discrete Methods, 1 (1980). [101] B. Wu and K. Chao, Spanning Trees and Optimization Problems, Discrete Mathematics and Its Applications, Chapman & Hall/CRC, 2004. [102] B.-Y. Wu, Approximation algorithms for the optimal p-source communication spanning tree, Discrete Applied Mathematics, 143 (2004), pp. 31-42. [103] B. Y. Wu, An optimal algorithm for the maximum-density path in a tree, Information Processing Letters, 109 (2009), pp. 975-979. [104] B.-Y. Wu, K.-M. Chao, and C.-Y. Tang, Light graphs with small routing cost, Networks, 39, p. 2002. [105] B. Y. Wu, K.-M. Chao, and C. Y. Tang, An e cient algorithm for the length-constrained heaviest path problem on a tree, Information Processing Letters, 69 (1999), pp. 63-67. [106] B.-Y. Wu, K.-M. Chao, and C.-Y. Tang, A polynomial time approximation scheme for optimal product-requirement communication spanning trees, Journal of Algorithms, 36 (2000), pp. 182-204. [107] B.-Y. Wu, G. Lancia, V. Bafna, K.-M. Chao, R. Ravi, and C.-Y. Tang, A polynomial-time approximation scheme for minimum routing cost spanning trees, SIAM Journal on Computing, 29 (1999), pp. 761-778. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65696 | - |
| dc.description.abstract | 在這份學位論文裡，我們從演算法的角度來考慮資源分配問題。 在具有區域限制條件的資源分配問題裡，資源只能在相鄰的物件之間被配置； 而在全域資源分配裡，資源則可以被包裝、藉由中繼轉運點由來源地被運送到目的地。對於區域資源分配以及全域資源運用這兩大類問題，我們分別提出了抽象化的數學模型、能透過理論被證明的良好演算方法、以及問題困難度的證明，藉以譜出對於這個複雜議題的一份完整而全面的研究。
在區域性的需求供給方面，我們考慮了一個支配集問題在``衍生'這個概念底下的推廣問題。 我們稱之為``有容量的支配集問題'。首先，在不預設任何條件的一般圖形上，我們提出了能與傳統支配集問題的近似演算法相匹配、且以無窮漸近的角度來看是最佳的近似演算法。 除此之外，在一些圖形集合，例如：樹、樹寬度有上限的圖形、以及平面圖等之上，一系列的困難度證明，指出了我們所考慮的這個問題，在本質上比傳統支配集問題更為困難與複雜。 除了困難度的證明之外，對於這些圖形的集合，我們也提出了相對應的近似演算方法。 在全域的資源運用方面，作為研究複雜全域分配最佳化的起始橋樑，我們首先考慮無迴圈的子網路建構及維護問題。 在這個問題裡，我們希望這個無迴圈的子網路，在以距離作為加權的平均度量底下，能夠良好地保持與原本差距不大的距離空間。 對於建構及維護這樣的子網路，我們分別提出了有效率並且具有良好理論保證的演算方法。接著，我們進一步將每個連接所需的花費及效能納入考量，在最大化投資報酬率的概念底下，研究``最佳花費與效能比例'的子網路建構問題。 在這個議題底下，針對不同的參數要求、以及不同的結構條件限制，我們做了一個全面性的討論與研究。 | zh_TW |
| dc.description.abstract | This dissertation addresses resource allocation from an algorithmic perspective. Starting from resource allocations with locality constraints, in which resource assignments are valid only between adjacent objects, to global resource planning for which the resources can be packed and delivered via intermediate stops to demanding targets, we present algorithmic results with solid theoretical guarantees as well as hardness proofs to jointly compose a comprehensive study for the entire problem.
In terms of local demand supplying, we consider a generalization of the dominating set problem under the concept of capacitataion, namely, the capacitated domination problem. On one hand, approximation algorithms matching the classical bounds for the dominating set problem which are proven to be optimal in an asymptotic sense are presented for general graphs. On the other hand, a series of hardness results for trees, graphs of bounded treewidths, and planar graphs is presented to show that the considered problem is fundamentally more difficult than the extensively-studied dominating set problem, whereas corresponding approximation algorithms for these three graph classes are also provided. In terms of global resource planning, as an initiative step to the intricate global optimization, we first consider the construction and maintenance problem of acyclic networks which well-preserve the distance metric of the original space in a distance-weighted average sense. Efficient algorithms with quality guarantees for both problems are presented. Second, taking the expense and the impact of each link construction into consideration, we consider the problem of cost-efficient network construction, in the sense of maximizing the return of investments. A comprehensive study regarding different parametric requirements and structural constraints is presented. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T23:59:43Z (GMT). No. of bitstreams: 1 ntu-101-D97922021-1.pdf: 1449321 bytes, checksum: 66815bf96728f1a021f8707837e8e11c (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | Contents
口試委員會審定書. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Chinese Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii English Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv I Resource Allocation as an Algorithmic Problem 1 1 Background and Motivation 2 Organization of this Dissertation . . . . . . . . . . . . . . . . . . . . . 8 2 Notations and Preliminary Ground Knowledge 9 2.1 Algorithms and Computational Complexity . . . . . . . . . . . . . 9 2.2 Fundamental Graph Theory . . . . . . . . . . . . . . . . . . . . . 15 2.3 Linear Programs and the Duality . . . . . . . . . . . . . . . . . . 23 2.4 Fixed-Parameter Tractability . . . . . . . . . . . . . . . . . . . . . 28 2.5 Metric Space and Metric Embedding . . . . . . . . . . . . . . . . 32 3 Local Demand and Supply 35 3.1 Capacitated Domination . . . . . . . . . . . . . . . . . . . . . . . 35 3.1.1 Problem Denition . . . . . . . . . . . . . . . . . . . . . . 35 3.1.2 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . 37 3.2 Summary of the Results Obtained . . . . . . . . . . . . . . . . . . 38 4 Global Demand and Supply 41 4.1 Metric Embeddings of Low Distance-Weighted Average Stretch . . 42 4.1.1 Problems Addressed . . . . . . . . . . . . . . . . . . . . . 43 4.1.2 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . 44 4.2 Cost-Efficiency Maximization . . . . . . . . . . . . . . . . . . . . 46 4.2.1 Problems Addressed . . . . . . . . . . . . . . . . . . . . . 47 4.2.2 State of the Art . . . . . . . . . . . . . . . . . . . . . . . . 49 4.3 Summary of the Results Obtained . . . . . . . . . . . . . . . . . . 51 II Capacitated Domination Problem 54 5 Approximation Algorithms for General Graphs 55 5.1 ln n-Approximation for Inseparable Demand . . . . . . . . . . . . 56 5.2 (4 ln n + 2)-Approximation for Separable Demand . . . . . . . . . 58 5.3 (2 ln n + 1)-Approximation for Separable Demand with Unit Cost 64 5.4 Delta*-approximation for Separable Demand . . . . . . . . . . . . . . 66 5.4.1 Primal/Dual Linear Programs . . . . . . . . . . . . . . . . 67 5.4.2 The Greedy Charging Algorithm . . . . . . . . . . . . . . . 68 6 Graphs of Bounded Treewidth 73 6.1 W[1]-Hardness with respect to Treewidth . . . . . . . . . . . . . . 73 6.2 Fixed-Parameter Tractability with respect to Treewidth and Maximum Capacity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.3 A Constant Factor Approximation for Outerplanar Graphs with Separable Demand . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.3.1 The Structure - General Ladders . . . . . . . . . . . . . . . 81 6.3.2 Removing More Edges . . . . . . . . . . . . . . . . . . . . 87 6.3.3 Rened Charging Scheme . . . . . . . . . . . . . . . . . . . 90 6.3.4 Overall Analysis . . . . . . . . . . . . . . . . . . . . . . . . 92 7 Planar Graphs 94 7.1 A Well-Known Framework - from Bounded Treewidth to Planar . 94 7.2 A Constant Factor Approximations for Separable Demand . . . . 96 7.3 (3/2-epsilon)-Approximation Threshold for Inseparable Demand . . . . 98 8 Other Algorithmic Results for Trees with Unit Vertex Cost 100 8.1 A Linear Time Algorithm for Inseparable Demand . . . . . . . . . 100 8.2 NP-Completeness for Separable Demand . . . . . . . . . . . . . . 103 8.3 A Polynomial Time Approximation Scheme for Separable Demand 106 8.3.1 Relaxed Knapsack Problem . . . . . . . . . . . . . . . . . 106 8.3.2 A Pseudo-Polynomial Time Algorithm . . . . . . . . . . . 111 8.3.3 Extension to Polynomial-Time Approximation Scheme . . 113 III Quality Backbone Design and Maintenance 115 9 Building Acyclic Backbones with Low DWA-Stretch 116 9.1 A Point-Set Cutting Lemma . . . . . . . . . . . . . . . . . . . . . 116 9.1.1 Proof of the Cutting Lemma . . . . . . . . . . . . . . . . . 117 9.1.2 Computing the Optimal Cut in Linear Time . . . . . . . . 123 9.2 Approximating Arbitrary Metrics . . . . . . . . . . . . . . . . . . 124 9.3 Approximating Euclidean Metrics by Their Spanning Trees . . . . 127 10 Maintaining Acyclic Backbones under Link Failures 132 10.1 An Optimal Algorithm for Arbitrary Distance Functions . . . . . 132 10.2 An Efficient Algorithm for Euclidean Metrics . . . . . . . . . . . . 135 10.3 General Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138 11 Cost-Efficient Bi-Constrained Backbone Construction 140 11.1 Cost-Efficiency Maximization for Trees and Almost-Trees . . . . . 142 11.2 Graphs of Bounded Treewidth . . . . . . . . . . . . . . . . . . . . 148 11.3 A Fully Polynomial-Time Approximation Scheme for the Relaxed Cost-Eciency Maximization Problem . . . . . . . . . . . . . . . 153 12 Maximizing Cost-Efficiency under Structural Constraints 160 12.1 A Parametric Searching Approach and its Application . . . . . . . 160 12.2 General Steiner Constraints . . . . . . . . . . . . . . . . . . . . . 167 IV Concluding Remarks 174 Discussions and Open Problems . . . . . . . . . . . . . . . . . . . . . . 175 Future Research Topics and Further Extensions . . . . . . . . . . . . . 178 Bibliography 179 Indexes 190 | |
| dc.language.iso | zh-TW | |
| dc.subject | 有容量的支配集 | zh_TW |
| dc.subject | 投資效能最佳化 | zh_TW |
| dc.subject | 低延展空間鑲嵌 | zh_TW |
| dc.subject | 資源分配 | zh_TW |
| dc.subject | Resource Allocation | en |
| dc.subject | Capacitated Domination | en |
| dc.subject | Low-Stretch Embedding | en |
| dc.subject | Cost-Efficiency Maximization | en |
| dc.title | 以演算法的角度探討區域及全域資源分配 | zh_TW |
| dc.title | An Algorithmic Approach to Local and Global Resource Allocations | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 陳健輝,趙坤茂,劉邦鋒,張鎮華,陳建佳 | |
| dc.subject.keyword | 資源分配,有容量的支配集,低延展空間鑲嵌,投資效能最佳化, | zh_TW |
| dc.subject.keyword | Resource Allocation,Capacitated Domination,Low-Stretch Embedding,Cost-Efficiency Maximization, | en |
| dc.relation.page | 191 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-07-17 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 未授權公開取用 | 1.42 MB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。