趙坤茂臺灣大學:資訊工程學研究所王弘倫Wang, Hung-LungHung-LungWang2010-06-022018-07-052010-06-022018-07-052008U0001-1507200811491100http://ntur.lib.ntu.edu.tw//handle/246246/184837Facility location problems arise in many fields such as operations research, communication, and theoretical computer science. Conventionally, depending on the requirements,acility location problems are categorized into two groups. One is the center problem, and the other is the median problem. Based on these two formulations, we investigaten this dissertation some extensions on tree networks: the backup facility location problems, the facility-centric facility location problems, and the dynamic facility locationroblems. Given that a facility may fail with a given probability, the goal of a backup facility location problem is to find a deployment such that the expected value of a given objective function is optimized. In a facility-centric facility location problem, the goal is to find the orbits and locations of all facilities such that a given objective function assumes its optimal value. In a dynamic facility location problem, the given network changes with time, and the goal is to maintain the facility of each part in the network efficiently.1 Introduction . . . . . . . . . . . 1.1 Facility Location Problems . . . . . . . . . . . . . . 1.2 Graph-Theory Terminology . . . . . . . . . . . . . . . 5.3 Historical Review and Contributions in the Dissertation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 The Backup 2-Center and Backup 2-Median Problems on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13.1 Problem Definitions . . . . . . . . . . . . . . . . . 14.2 A Linear Time Algorithm for the Backup 2-Center Problem on Trees . . . . . . . . . . . . . . . . . . . . . . . . 16.3 An O(n log n)-Time Algorithm for the Backup 2-Median Problem on Trees . . . . . . . . . . . . . . . . . . . . 29 The 2-Radius and 2-Radiian Problems on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.1 Problem Definitions and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 A Linear Time Algorithm for the 2-Radius Problem on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45.3 An O(n log n)-Time Algorithm for the 2-Radiian Problem on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 49.4 The V (T)=V (T)=2 Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56.5 The Lower Bound for the 2-Radiian Problem on Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 Maintaining Centdians in a Fully Dynamic Forest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.1 Problem Definition and Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.1.1 Problem Definition and the Properties of a Centdian in a Tree . . . . . . . . . . . . . . . . . . . . . . . . . 63.1.2 Topology Trees and Top Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64.2 The Tree Transformation and the Modification of Topology Trees . . . . . . . . . . . . . . . . . . . . . . . . . . 68.2.1 Transforming the Input Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69.2.2 Maintaining the Topology Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74.3 Maintaining the Centdians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77.4 Optimality of the Dynamic Centdian Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 Conclusions . . . . . . . . . . . . . . . . . . . . . . 82.1 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83ibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85application/pdf540965 bytesapplication/pdfen-US設施配置問題中心重心樹狀網路facility location problemcentermediancentdiantreethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/184837/1/ntu-97-F92922085-1.pdf