我們研究在給定的路徑圖上如何找出一個機構的anti-k-centrum 位址。意思是說,路徑圖上每一頂點到此機構的加權距離,取前k 小的值加總要最大。 我們提出了兩種類似的演算法,第一個演算法我們將所想到的方式一步一步執行,其時間複雜度取決於所使用的k-level 演算法。Timothy 提出一隨機演算法求k-level,時間複雜度為O(n log n + nk1/3),由Dey 證明在最壞狀況下k-level 的轉折點個數為m = O(nk1/3),n是路徑圖的頂點個數,k 是一小於n 的常數。 第二個演算法利用了動態優先權序列來求解,時間複雜度為O(T(n; n + m)),其中T(n;m) = O(m (n)), (n) 表示一逆阿克曼函數。
In this thesis, we plan to find a facility placed on the edge of a given path, which meets the demand constraints of anti-k-centrum location problem. We provide two algorithms to solve the problem. The first algorithm uses k-level algorithm helping us, the time complexity of the first algorithm depends on the speed of constructing the k-level. Timothy showed a randomized algorithm constructing the k-level, that runs an expected time O(n log n + nk1/3), n is the number of vertices on the given path, with the bound by Dey showing that the number of turning points on k-level is m = O(nk1/3) in the worst case. The second algorithm uses an abstract data structure call kinetic priority queue. The time complexity is O(T(n,n+m)),which T(n,m) = O(m (n)), and (n) denote the inverse Ackermann function.