Improved Algorithms for the Minmax-Regret 1-Center and 1-Median Problems

最小後悔設施放置問題之改進演算法

游弘毅(Hung-I Yu)

指導教授 ： 王炳豐

國立清華大學/電機資訊學院/資訊工程學系/博士(2008年)

摘要

Over three decades, location problems on networks have received much attention from researchers in the fields of transportation and communication. Traditionally, network location theory has been concerned with networks in which the vertex weights and edge lengths are known precisely. However, in practice, it is often impossible to obtain precise estimates of all parameters of the network model, since real data often involve a significant portion of uncertainty. Recently, many researchers have turned their attention to a new approach for handling uncertainty, which is called the minmax-regret approach. The concept of this approach is to minimize the worst-case loss in the objective function that may occur because of the uncertain parameters.
In this dissertation, we examine the 1-center and 1-median problems on the minmax-regret model, and present efficient algorithms for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from O(mn^2 log n) to O(mn log n). For the problem on a tree, we improve the upper bound from O(n^2) to O(n log^2 n). For the minmax-regret 1-median problem on a general graph, we improve the upper bound from O(mn^2 log n) to O(mn^2 + n^3 log n). For the problem on a tree, we improve the upper bound from O(n log^2 n) to O(n log n).

關鍵字

設施放置問題 ； 最小後悔之最佳化 ； 圖 ； 樹 ； HASH(0x1cf0c990) ； HASH(0x1cf0ca30)

並列摘要

「設施放置問題」考慮的是在網路中尋找一個新設施的最佳放置地點。這一類問題的探討，不論就理論研究或實際應用而言，都具有相當的重要性。在傳統的網路設施放置問題中，一般會假設節點的權重及邊的長度這些參數都可以被精確的量測。然而實際生活中所蒐集到的資料通常有許多的不確定性，因此在考慮設施的最佳位置時，我們幾乎不可能得到這些網路參數的確實數值。近年來在設施放置問題的這個研究領域裡，有一類新的主題興起，稱為「最小後悔設施放置問題」。這個主題是為了實際符合網路環境的不確定性所產生，與傳統問題相較，更具有實用價值，所以吸引了許多學者的注意。
這篇論文研究的是最小後悔設施放置問題中最基本的兩個問題：the minmax-regret 1-center 問題和 the minmax-regret 1-median 問題，並探討在網路上節點權重有不確定性存在時的情況。我們在兩類最常見的網路上，對這兩個問題提出比既有方法更快速的演算法。就 the minmax-regret 1-center problem而言，在 general graph 上這個問題的時間複雜度被我們加快了 O(n) 倍，由原本的 O(mn^2 log n) 降到 O(mn log n)；在 tree 上的時間也由原本的 O(n^2) 被加速到 O(n log^2 n)。就 the minmax-regret 1-median problem而言，在 general graph 上，我們將原本的 O(mn^2 log n)-time 演算法改善到 O(mn^2 + n^3 log n) time；而在 tree 上的時間也由原本的 O(n log^2 n) 進一步的減少到 O(n log n)。

並列關鍵字

location theory ； minmax-regret optimization ； centers ； medians ； general graphs ； trees

參考文獻

[6] Arora, S., Raghavan, P., and Rao, S., "Approximation schemes for Euclidean k-median and related problems," In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, ACM, New York, 106-113, 1998.

[1] Agarwal, P. K. and Procopiuc, C. M., "Exact and approximation algorithms for clustering," Algorithmica, vol. 33, 201-226, 2002.

[2] Agarwal, P. K. and Sharir, M., "Efficient algorithms for geometric optimization," ACM Computing Surveys, vol. 30, no. 4, 412-458, 1998.

[4] Andreatta, G. and Mason, F. M., "k-eccentricity and absolute k-centrum of a tree," European Journal of Operational Research, vol. 19, 114-117, 1985.

[5] Andreatta, G. and Mason, F. M., "Properties of the k-centrum in a network," Networks, vol. 15, 21-25, 1985.