臺灣博碩士論文加值系統

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).

「設施放置問題」考慮的是在網路中尋找一個新設施的最佳放置地點。這一類問題的探討，不論就理論研究或實際應用而言，都具有相當的重要性。在傳統的網路設施放置問題中，一般會假設節點的權重及邊的長度這些參數都可以被精確的量測。然而實際生活中所蒐集到的資料通常有許多的不確定性，因此在考慮設施的最佳位置時，我們幾乎不可能得到這些網路參數的確實數值。近年來在設施放置問題的這個研究領域裡，有一類新的主題興起，稱為「最小後悔設施放置問題」。這個主題是為了實際符合網路環境的不確定性所產生，與傳統問題相較，更具有實用價值，所以吸引了許多學者的注意。
這篇論文研究的是最小後悔設施放置問題中最基本的兩個問題：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)。

Abstract i
Acknowledgement iii
Contents iv
List of Figures vi
List of Tables viii
Chapter 1 Introduction 1
1.1 Related Work 5
1.2 Summary of Results 7
1.3 Dissertation Organization 9
Chapter 2 Notation and Preliminaries 10
Chapter 3 The Minmax-Regret 1-center Problem on a General Graph 15
3.1. Averbakh and Berman’s Algorithm 15
3.2. An Improved Algorithm 17
Chapter 4 The Minmax-Regret 1-center Problem on a Tree 28
4.1. Preprocess 28
4.2. An Improved Algorithm 33
Chapter 5 The Minmax-Regret 1-median Problem on a General Graph 41
5.1. Averbakh and Berman's Algorithm 41
5.2. An Improved Algorithm 45
Chapter 6 The Minmax-Regret 1-median Problem on a Tree 48
6.1. Averbakh and Berman's Algorithm 48
6.2. An Improved Algorithm 52
6.2.1. Computing Medians 53
6.2.2. The New Approach 60
Chapter 7 Conclusion and Future Work 63
References 65

[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.
[3] Alstrup, S., Lauridsen, P. W., Sommerlund, P., and Thorup, M., "Finding cores of limited length," Technical Report, the IT University of Copenhagen, 2001. (A preliminary version appeared in Proceedings of the 5th International Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, vol. 1272, pp. 45-54, 1997.)
[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.
[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.
[7] Averbakh, I., "Minmax regret solutions for minimax optimization problems with uncertainty," Operations Research Letters, vol. 27, no. 2, 57-65, 2000.
[8] Averbakh, I., "Complexity of robust single-facility location problems on networks with uncertain lengths of edges," Discrete Applied Mathematics, vol. 127, no. 3, 505-522, 2003.
[9] Averbakh, I., "The minimax relative regret median problem on networks," INFORMS Journal on Computing, vol. 17, no. 4, 451-461, 2005.
[10] Averbakh, I. and Bereg, S., "Facility location problems with uncertainty on the plane," Discrete Optimization, vol. 2, no. 1, 3-34, 2005.
[11] Averbakh, I. and Berman, O., "Minimax regret p-center location on a network with demand uncertainty," Location Science, vol. 5, no. 4, 247-254, 1997.
[12] Averbakh, I. and Berman, O., "Algorithms for the robust 1-center problem on a tree," European Journal of Operational Research, vol. 123, no. 2, 292-302, 2000.
[13] Averbakh, I. and Berman, O., "Minmax regret median location on a network under uncertainty," Informs Journal on Computing, vol. 12, no. 2, 104-110, 2000.
[14] Averbakh, I. and Berman, O., "An improved algorithm for the minmax regret median problem on a tree," Networks, vol. 41, no. 2, 97-103, 2003.
[15] Ben-Moshe, B., Bhattacharya, B. K., and Shi, Q., "An optimal algorithm for the continuous/discrete weighted 2-center problems in trees," in Proceedings of the 7th Latin American Theoretical Informatics Symposium, Lecture Notes on Computer Science, vol. 3887, 166-177, 2006.
[16] Brodal, G., Georgiadis, L., and Katriel, I., "An O(n log n) version of the Averbakh-Berman algorithm for the robust median of a tree," Operations Research Letters, vol. 36, no. 1, 14-18, 2008.
[17] Burkard, R. E. and Dollani, H., "A note on the robust 1-center problem on trees," Annals of Operations Research, vol. 110, no. 1, 69-82, 2002.
[18] Burkard, R. E. and Dollani, H., "Robust location problems with pos/neg weights on a tree," Networks, vol. 38, no. 2, 102-113, 2001.
[19] Burkard, R. E., Dollani, H., Lin, Y., and Rote, G., "The obnoxious center problem on a tree," SIAM Journal on Discrete Mathematics, vol. 14, no. 4, 498-509, 2001.
[20] Cappanera P, "A survey on obnoxious facility location problems," Technical Report, TR-99-11, Dipartimento di Informatica, Universita di Pisa, 1999.
[21] Carrizosa, E. J., Conde, E., Fern�鴨dez, F. R., and Puerto, J., "An axiomatic approach to the cent-dian criterion," Location Science, vol. 3, 1-7, 1994.
[22] Charikar, M., Chekuri, C., Goel, A., and Guha, S., "Rounding via trees: deterministic approximation algorithms for group steiner trees and k-median," in Proceedings of the 30th ACM Symposium on Theory of Computing, ACM, New York, 114-123, 1998.
[23] Charikar, M., Guha, S., Tardos, ��, and Shmoys, D. B., "A constant-factor approximation algorithm for the k-median problem," Journal of Computer and System Sciences, vol. 65, no. 1, 129-149, 2002.
[24] Chen, B. and Lin, C.-S., "Minmax-regret robust 1-median location on a tree," Networks, vol. 31, no. 2, 93-103, 1998.
[25] Church R. L. and Garfinkel R. S., "Locating an obnoxious facility on a network," Transportation Science, vol. 12, 107-118, 1978.
[26] Cole, R., "Slowing down sorting networks to obtain faster sorting algorithms," Journal of the ACM, vol. 34, 200-208, 1987.
[27] Conde, E., "A note on the minmax regret centdian location on trees," Operations Research Letters, vol. 36, no. 2, 271-275, 2008.
[28] Conde, E., "Minmax regret location-allocation problem on a network under uncertainty," European Journal of Operational Research, vol. 179, no. 3, 1025-1039, 2007.
[29] Daskin, M. S., Network and discrete location: models, algorithms, and applications, Wiley, New York, 1995.
[30] Drezner, Z., Facility location. A survey of applications and methods, Springer, New York, 1995.
[31] Drezner, Z., "Sensitivity analysis of the optimal location of a facility," Naval Research Logistics Quarterly, vol. 33, 209-224, 1980.
[32] Drezner, Z. and Hamacher, H. W., Facility location: applications and theory, Springer-Verlag, New York, 2002.
[33] Drezner, Z. and Wesolowsky, G. O., "Location of multiple obnoxious facilities," Transportation Science, vol. 19, 193-202, 1985.
[34] Dyer, M. E., "On a multidimensional search technique and its application to the Euclidean one-centre problem," SIAM Journal on Computing, vol. 15, 725-738, 1986.
[35] Fern�鴨dez, F. R., Nickel, S., Puerto, J., and Rodr�櫂uez-Ch�朦, A. M., "Robustness in the Pareto-solutions for the multi-criteria minisum location problem," Journal of Multicriteria Decision Analysis, vol. 10, no. 4, 191-203, 2001.
[36] Francis, R. L., Lowe, T. J., and Tamir, A., "Aggregation error bounds for a class of location models," Operations Research, vol. 48, 294–307, 2000.
[37] Frank, H., "Optimum locations on a graph with probabilistic demands," Operations Research, vol. 14, 409-421, 1966.
[38] Frank, H., "Optimum locations on a graph with correlated normal demands," Operations Research, vol. 14, 552-557, 1967.
[39] Frederickson, G. N., "Optimal parametric search algorithms in trees II: p-center problems and check points," Technical Report, Purdue University, 1992.
[40] Frederickson, G. N. and Johnson, D. B., "Finding kth paths and p-centers by generating and searching good data structures," Journal of Algorithms, vol. 4, pp. 61-80, 1983.
[41] Gabow, H. N. and Tarjan, R. E., "A linear-time algorithm for a special case of disjoint set union," Journal of Computer and System Sciences, vol. 30, no. 2, 209-221, 1985.
[42] Gavish, B. and Sridhar, S., "Computing the 2-median on tree networks in O(n log n) time," Networks, vol. 26, 305-317, 1995.
[43] Goldman, A. J., "Optimal center location in simple networks," Transportation Science, vol. 5, 212-221, 1971.
[44] Hakimi, S. L., "Optimal locations of switching centers and the absolute centers and medians of a graph," Operations Research, vol. 12, 450-459, 1964.
[45] Halpern, J., "The location of a cent-dian convex combination on an undirected tree," Journal of Regional Science, vol. 16, 237-245, 1976.
[46] Halpern, J., "Finding minimal center-median convex combination (cent-dian) of a graph," Management Science, vol. 24, no. 5, 535-547, 1978.
[47] Halpern, J., "Duality in the cent-dian of a graph," Operations Research, vol. 28, 722-735, 1980.
[48] Hsu, W. L., "The distance-domination numbers of trees," Operations Research Letters, vol. 1, 96-100, 1982.
[49] Hwang, R. Z., Lee, R. C. T., and Chang, R. C., "The searching over separators strategy to solve some NP-hard problems in subexponential time," Algorithmica, vol. 9, 398-423, 1993.
[50] Hwang, R. Z., Lee, R. C. T., and Chang, R. C., "The slab dividing approach to solve the Euclidean p-center problem," Algorithmica, vol. 9, 1-22, 1993.
[51] Jain, K. and Vazirani, V. V., "Approximation algorithms for metric facility location and k-Median problems using the primal-dual schema and Lagrangian relaxation," Journal of the ACM, vol. 48, no. 2, 274-296, 2001.
[52] Kalcsics, J., Nickel, S., Puerto, J., and Tamir, A., "Algorithmic results for ordered median problems defined on networks and the plane," Operations Research Letters, vol. 30, 149-158, 2002.
[53] Kariv, O. and Hakimi, S. L., "An algorithmic approach to network location problems. I: The p-centers," SIAM Journal on Applied Mathematics, vol. 37, no. 3, 513-538, 1979.
[54] Kariv, O. and Hakimi, S. L., "An algorithmic approach to network location problems. II: The p-medians," SIAM Journal on Applied Mathematics, vol. 37, no. 3, 539-560, 1979.
[55] Kouvelis, P., Vairaktarakis, G., and Yu, G., "Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty," Working Paper 93/94-3-4, Department of Management Science and Information Systems, Graduate School of Business, The University of Texas at Austin, 1994.
[56] Kouvelis, P. and Yu, G., Robust discrete optimization and its applications, Kluwer Academic Publishers, Dordrecht, 1997.
[57] Ku, S.-C., Lu, C.-J., Wang, B.-F., and Lin, T.-C., "Efficient algorithms for two generalized 2-median problems on trees," in Proceedings of the 12th International Symposium on Algorithms and Computation, Lecture Notes on Computer Science, vol. 2223, 768-778, 2001.
[58] Labb��, M., Peeters, D., and Thisse, J.-F., "Location on networks," in Handbooks in OR & MS, vol. 8, Ball, M. O., editors, Elsevier, Amsterdam, 1995.
[59] Labb��, M., Thisse, J.-F., and Wendell, R., "Sensitivity analysis in minisum facility location problems," Operations Research, vol. 38, 961-969, 1991.
[60] Megiddo, N., "Linear-time algorithms for linear-programming in R3 and related problems," SIAM Journal on Computing, vol. 12, no. 4, 759-776, 1983.
[61] Megiddo, N. and Supowit, K. J., "On the complexity of some common geometric location problems," SIAM Journal on Computing, vol. 13, 182-196, 1984.
[62] Megiddo, N. and Tamir, A., "New results on the complexity of p-center problems," SIAM Journal on Computing, vol. 12, no. 4, 751-758, 1983.
[63] Megiddo, M., Tamir, A., Zemel, E., and Chandrasekaran, R., "An O(n log2 n) algorithm for the kth longest path in a tree with applications to location problems," SIAM Journal on Computing, vol. 10, no. 2, 328-337, 1981.
[64] Minieka, E., "Anticenters and antimedians of a network," Networks, vol. 13, 359-364, 1983.
[65] Mirchandani P. B. and Francis R. L., Discrete location theory, Wiley, New York, 1990.
[66] Mirchandani, P. B. and Odoni, A. R., "Location of medians on stochastic networks," Transportation Science, vol. 13, 85-97, 1979.
[67] Mirchandani, P. B., Oudjit, A., and Wong, R. T., "Multidimensional extensions and a nested dual approach for the M-median problem," European Journal of Operational Research, vol. 21, 121-137, 1985.
[68] Nickel, S., "Discrete ordered Weber problems," In Operations Research Proceedings 2000, Fleischmann, B., Lasch, R., Derigs, U., Domschke, W., and Rieder, U., editors, Springer, Berlin, 71–76, 2001.
[69] Nickel, S. and Puerto, J., "A unified approach to network location problems," Networks, vol. 34, 283-290, 1999.
[70] Nickel, S. and Puerto, J., Location Theory: A unified approach, Springer-Verlag, Heidelberg, Germany, 2005.
[71] Nikulin, Y., "Robustness in combinatorial optimization and scheduling theory: an annotated bibliography," http://www.optimization-online.org/DB_HTML/ 2004/11/995.html, 2004.
[72] Oudjit, A., "Median locations on deterministic and probabilistic multidimensional networks," PhD Dissertation, Rennselaer Polytechnic Institute, Troy, 1981.
[73] P�臆ez-Brito, D. and Moreno-P�臆ez, J. A., "The generalized p-centdian on network," Top, vol. 8, no. 2, 265-285, 2000.
[74] Puerto, J. and Rodr�櫂uez-Ch�朦, A. M., "Robust positioning of service units," Stochastic Models, vol. 19, no. 1, 125-147, 2003.
[75] Puerto, J., Rodr�櫂uez-Ch�朦, A. M., and Tamir, A., "New results on minimax regret single facility ordered median location problems on networks," in Proceedings of the 15th Annual European Symposium on Algorithms, Lecture Notes on Computer Science, vol. 4698, 230-240, 2007.
[76] Rodr�櫂uez-Ch�朦, A. M., Nickel, S., Puerto, J. and Fern�鴨dez, F. R., "A flexible approach to location problems," Mathematical Methods of Operations Research, vol. 51, no. 1, 69-89, 2000.
[77] Slater, P. J., "Centers to centroids in a graph," Journal of Graph Theory, vol. 2, 209-222, 1978.
[78] Synder, L., "Facility location under uncertainty: A review," IIE Transactions, vol. 38, no. 7, 547-564, 2006.
[79] Tamir, A., "An O(pn2) time algorithm for the p-median and related problems on tree graphs," Operations Research Letters, vol.19, no. 2, pp. 59-64, 1996.
[80] Tamir, A., "Improved complexity bounds for center location problems on network by using dynamic data structures," SIAM Journal on Discrete Mathematics, vol. 1, no. 3, 377-396, 1988.
[81] Tamir, A., "Obnoxious facility location on graphs," SIAM Journal on Discrete Mathematics, vol. 4, no. 4, 550-567, 1991.
[82] Tamir, A., "The k-centrum multi-facility location problem," Discrete Applied Mathematics, vol. 109, 293-307, 2001.
[83] Ting, S. S., "A linear time algorithm for maxisum facility location on tree networks," Transportation Science, vol. 18, 76-84, 1984.
[84] Tamir, A., P�臆ez-Brito, D., and Moreno-P�臆ez, J. A., "A polynomial algorithm for the p-centdian problem on a tree," Networks, vol. 32, 255-262, 1998.
[85] Wang, B.-F., Ku, S.-C., and Shi, K.-H., "Cost-optimal parallel algorithms for the tree bisector and related problems," IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 9, 888-898, 2001.
[86] Weaver, J. R. and Church, R. L., "Computational procedures of location problems on stochastic networks," Transportation Science, vol. 17, 168-180, 1983.
[87] Vairaktarakis, G. L. and Kouvelis, P., "Incorporation dynamic aspects and uncertainty in 1-median location problems," Naval Research Logistics, vol. 46, 147-168, 1999.
[88] Yu, H.-Y. and Wang, B.-F., "An improved algorithm for finding k-centrums on weighted trees," in Proceedings of the 9th International Conference on Parallel and Distributed Systems, 222-225, 2002.