於圖形模式上配置穩健設施之演算法

Abstract

本論文主要的內容是於樹狀圖形上討論穩健中心問題(robust p- center problem)以及在一般圖形上討論多服務中心問題(Multi-Service p-Center Problem)，並且提出了一些開創性的結果。 穩健中心問題可以視為傳統中心問題(classical p-center problem)的 推廣，其定義如下：給定一個具有不確定參數的圖形，其節點的權 重以及邊的長度並不是定值，而是可以各在一事先給定的範圍內變 化，而這樣的變化可以是任意的，不受任何機率分布限制。一組情 境(scenario)就是針對所有節點和邊在其允許範圍內各指定一固定的數 值，如同前面所述，因為這些數值可以在其範圍內任意變化，所以情 境的總數是無限的。因為在某一特定的情境下，所有可變的參數均被 設為定值，我們就可以針對某一給定的點集合定義其客觀值(objective value)。對於一給定的點集合來說，在某一情境下的後悔值(regret)定 義為此集合的客觀值減去該情境下的最佳值，因此對於點集合來說， 後悔值越大代表此集合在該情境下相對上來說越差，而且針對不同的 情境，同一個點集合可以有不同的後悔值。對某個點集合來說，造成 其後悔值最大的情境稱為最差情境(worst-case scenario)，而穩健中心問 題的目標，就是希望能找出一組含p個點的集合(p為一給定的參數)，使 得在其最差情境之下的後悔值最小，我們稱此點集合為最佳點集。 針對此問題在樹狀圖形上，而且僅需找出某一最佳點(p=1)的情 況下，Burkard和Dollani [16]給了一個時間複雜度為O(n3 log n)的演算 法，在此n表示此圖形上的節點個數。他們提出來的演算法有兩個關鍵 性的步驟，其一就是將所需要探討的情境數量減少為O(n3)個並且可以 在O(n3 log n)時間內把這些情境全部計算出來；其二就是他們利用參 數搜尋(parametric search)的技巧，進一步將最佳點可能的範圍縮小到 某一區間之內，而這些動作需要O(log n)次可行性測試，並且每一次測 試需要花費O(n3)時間。在本論文中，我們改進了上述的步驟，我們發 現這些O(n3)個情境中有許多相似性，因此我們可以先把某一組情境計 算出來之後，以此為基礎，利用逐步更新的技巧在O(n3)時間內把所有 的情境算出來；另外，我們也把這些情境做適當的分組，利用每組之 內的結構性將可行性測試所需要的總時間減少到O(n2 log2 n)，因此藉 由這兩個改良技巧，我們可以把此問題的時間複雜度減少為O(n3)。 當我們需要找出多個最佳點而且給定的樹狀圖形只有節點的權重會 變化（邊的長度為定值）的情況下，Averbakh和Berman [5]提出了一個 時間複雜度為O(n2 log2 n log log n)的演算法，不過如果要把邊的長度 變化也列入考量，就我們所知，目前並沒有任何演算法可以找出兩個 以上點(p _ 2)的最佳點集。在本論文中，我們在一節點權重均相同、 邊的長度會變化的樹狀結構上討論了此問題，在點集合侷限於節點的 情況下，提出了第一個多項式時間的演算法用來求出恰含兩點的最佳 點集；我們也嘗試將前述的演算法推廣到求三個以上點的最佳點集， 並且指出一些本質上的困難。我們主要的貢獻就是探討對於某p個給 定的節點，其最差情境的性質。如同問題的定義所述，一旦我們了解 某p個給定節點的最差情境，我們就可以估算這組點集合的最大後悔 值，而我們可以將全部的情況列舉出來並且逐一計算其最大後悔值， 具有最小最大後悔值的p個節點就是最佳解。 另外我們也在一般圖形上討論多服務中心問題，這是一個基於現實 生活上的考量而定義的全新問題。在一般的電腦網路上，使用者可能 需要多個不同的服務，而這些服務可能必須由不同的伺服器提供，因 此使用者到全部伺服器的距離總和（我們稱為使用者總距離）就是一 個很重要的因素。多服務中心問題的目的就是嘗試找出p個伺服器的配 置位置，使得最遠的使用者總距離最小。我們利用一般圖形來模擬此 問題，同時我們也把節點權重的變化量列入考量，提出了一個輔助結 構可以有效簡化權重變化所造成的影響，因此我們的重點是在無參數 變化的圖形上討論此問題。我們也證明這個問題是NP困難問題，並且 提出了一個參數為p的近似演算法與線上演算法。

We present some results for the emph{robust $p$-center problem} on tree graphs and emph{Multi-Service $p$-Center Problem} on general graphs in this dissertation. The emph{robust $p$-center problem}, abbreviated as ROBCEN, which can be viewed as a generalization of the classical $p$-center problem, is defined as follows. Given is a graph with uncertain parameters, that is to say, each vertex weight (edge length, respectively) is associated with a feasible range and the exact value of each weight (length, respectively) can take any values within its corresponding range with unknown probability distributions. A emph{scenario} is a feasible assignment of all parameters to the vertices and edges, and the total number of possible scenarios is unbounded. The emph{regret} of a given set of facilities $X_p$ containing $p$ points under a scenario $s$ is the difference between the objective value of $X_p$ and the optimal value under $s$. In fact, $X_p$ may have different regrets under different scenarios. The scenario which makes $X_p$ attain the maximum regret is called the $emph{worst-case scenario}$ with respect to $X_p$. The objective of this problem is to find an optimal location $X_p^*$, called robust $p$-center, with minimum regret under its worst-case scenario. For the robust $1$-center problem (ROB1CEN) on tree graphs, that is to say, to locate a point $x^*$ with the same objective, Burkard and Dollani cite{Burkard2002} gave an $O(n^3 log n)$ time algorithm, where $n$ is the number of vertices. They first reduced the cardinality of the essential scenarios to $O(n^3)$ and generated them in $O(n^3 log n)$ time. Then, an approach based on the parametric search cite{Frederickson1991} was applied to further reduce the optimal edge (an edge contains $x^*$ and can be found in $O(n^2 log n)$ time cite{Averbakh2000a}) to a restricted interval containing $x^*$, in which only $O(n^3)$ linear functions are sufficient to locate $x^*$. This approach performed $O(log n)$ feasibility tests and each test took $O(n^3)$ time to check all $O(n^3)$ scenarios. In this dissertation, we propose a further improved algorithm that runs in $O(n^3)$ time to compute $x^*$ in the optimal edge. The improvement is assisted with two important observations of the $O(n^3)$ scenarios introduced by Burkard and Dollani cite{Burkard2002}. First, by exploiting the similarity among the scenarios, we are able to construct and preprocess a base scenario set so that the $O(n^3)$ essential scenarios can be generated by iteratively updating the base set in $O(n^3)$ time. Second, by considering these scenarios in groups and using structural properties within each group, we can reduce the time complexity of each feasibility test to $O(n^2 log n)$, and thus the parametric search approach for the optimal edge can be done in $O(n^3)$ time, i.e., $O(n^2 log^2 n)$ time for tests and $O(n^2 log n)$ time for overhead. Thus, the robust 1-center problem with both vertex and edge uncertainties can be solved in $O(n^3)$ time. For ROBCEN when $pgeq 2$, this problem on a tree graph can be solved in $O(n^2 log^2 n log log n)$ time cite{Averbakh1997} when only the vertex uncertainty is considered (the length of each edge is a fixed value). However, to the best of our knowledge, there are no results for this problem when the edge uncertainty is considered. In this dissertation, we address vertex ROBCEN, where the centers are only allowed to locate on vertex set, on a vertex unweighted tree graph with only edge uncertainty, and propose the first polynomial time algorithm for the vertex robust 2-center problem (ROB2CEN). Our main contribution is to explore the worst-case scenario for a given set of facilities. We observe that there exist some vertices which are closest to different facility under different scenarios. Moreover, we obtain some key properties that can explore the worst-case scenario for a given $X_2$. Although most of the properties can be generalized to ROBCEN for $pgeq 3$, there exist some intrinsical obstacles and we also present an example to illustrate them. Since the objective of this problem is to find an $X_p$ with minimum regret under its worst-case scenario, once the worst-case scenario for a given $X_p$ is clarified, we can iteratively choose all possible solutions and then examine their maximum regret respectively. The $X_p$ with minimum maximum regret is the optimal solution. In this dissertation, we present a new problem called emph{Multi-Service $p$-center Problem}, abbreviated as MSCP, which is motivated by the practical requirements of demanders. Take the client-sever computer network as an example. Clients usually require multiple services which have to be serviced by different facilities. Based on this observation, the (weighted) distances from a client to emph{all} servers are important factors. The objective of MSCP is to find a set of facilities as centers to minimize the maximum (weighted) client-to-all-facility distance. We also take the vertex uncertainty into consideration and propose an auxiliary transformation that can simplify the effect of the vertex uncertainty. Finally, we prove that finding a vertex $p$-center for MSCP is NP-hard on general graphs and present some approximation and online algorithms with $p$-approximation (competitive) guarantee.