路徑圖上anti-k-centrum 選址問題

The anti-k-centrum location problem on a path

謝名宣(Ming-Hsuan Hsieh)

指導教授 ： 趙坤茂

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2016年)

https://doi.org/10.6342/NTU201800472

摘要

我們研究在給定的路徑圖上如何找出一個機構的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) 表示一逆阿克曼函數。

關鍵字

路徑圖 ； 定址問題 ； 演算法 ； 動態優先權序列 ； 加權距離 ； k-level ； anti-k-centrum

並列摘要

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.

並列關鍵字

path ； location problem ； k-level ； anti-k-centrum ； kinetic priority queue ； algorithm ； weighted distance

參考文獻

[1] Julien Basch, Leonidas J. Guibas, and Ramkumar G.D. Reporting red-blue intersections between two sets of connected line segments. Algorithms —ESA ’96, pages 302–319, 1996.

[3] G. S. Brodal and R. Jacob. Dynamic planar convex hull. The 43rd Annual IEEE Symposium on Foundations of Computer Science, page 617–626, 2002.

[4] Rainer E. Burkard, Helidon Dollani, Yixun Lin, and Günter Rote. The obnoxious center problem on a tree. SIAM J. Discrete Math, 14:498–509, 2001.

[7] T. K. Dey. Improved bounds on planar k-sets and k-levels. In Proceedings 38th Annual Symposium on Foundations of Computer Science, pages 156–161, 1997.

[8] Csoke Meghan E. The facility location problem. All Student Theses, 2015.