Title

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

Translated Titles

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

Authors

游弘毅

Key Words

設施放置問題 ; 最小後悔之最佳化 ; 圖 ; 樹 ; HASH(0x1cf0c990) ; HASH(0x1cf0ca30) ; location theory ; minmax-regret optimization ; centers ; medians ; general graphs ; trees

PublicationName

清華大學資訊工程學系所學位論文

Volume or Term/Year and Month of Publication

2008年

Academic Degree Category

博士

Advisor

王炳豐

Content Language

英文

Chinese Abstract

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

English Abstract

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

Topic Category 基礎與應用科學 > 資訊科學
電機資訊學院 > 資訊工程學系所
Reference
  1. [1] Agarwal, P. K. and Procopiuc, C. M., "Exact and approximation algorithms for clustering," Algorithmica, vol. 33, 201-226, 2002.
    連結:
  2. [2] Agarwal, P. K. and Sharir, M., "Efficient algorithms for geometric optimization," ACM Computing Surveys, vol. 30, no. 4, 412-458, 1998.
    連結:
  3. [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.
    連結:
  4. [5] Andreatta, G. and Mason, F. M., "Properties of the k-centrum in a network," Networks, vol. 15, 21-25, 1985.
    連結:
  5. [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.
    連結:
  6. [7] Averbakh, I., "Minmax regret solutions for minimax optimization problems with uncertainty," Operations Research Letters, vol. 27, no. 2, 57-65, 2000.
    連結:
  7. [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.
    連結:
  8. [9] Averbakh, I., "The minimax relative regret median problem on networks," INFORMS Journal on Computing, vol. 17, no. 4, 451-461, 2005.
    連結:
  9. [10] Averbakh, I. and Bereg, S., "Facility location problems with uncertainty on the plane," Discrete Optimization, vol. 2, no. 1, 3-34, 2005.
    連結:
  10. [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.
    連結:
  11. [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.
    連結:
  12. [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.
    連結:
  13. [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.
    連結:
  14. [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.
    連結:
  15. [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.
    連結:
  16. [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.
    連結:
  17. [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.
    連結:
  18. [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.
    連結:
  19. [24] Chen, B. and Lin, C.-S., "Minmax-regret robust 1-median location on a tree," Networks, vol. 31, no. 2, 93-103, 1998.
    連結:
  20. [25] Church R. L. and Garfinkel R. S., "Locating an obnoxious facility on a network," Transportation Science, vol. 12, 107-118, 1978.
    連結:
  21. [26] Cole, R., "Slowing down sorting networks to obtain faster sorting algorithms," Journal of the ACM, vol. 34, 200-208, 1987.
    連結:
  22. [27] Conde, E., "A note on the minmax regret centdian location on trees," Operations Research Letters, vol. 36, no. 2, 271-275, 2008.
    連結:
  23. [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.
    連結:
  24. [31] Drezner, Z., "Sensitivity analysis of the optimal location of a facility," Naval Research Logistics Quarterly, vol. 33, 209-224, 1980.
    連結:
  25. [33] Drezner, Z. and Wesolowsky, G. O., "Location of multiple obnoxious facilities," Transportation Science, vol. 19, 193-202, 1985.
    連結:
  26. [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.
    連結:
  27. [35] Fern□ndez, F. R., Nickel, S., Puerto, J., and Rodr□guez-Ch□a, 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.
    連結:
  28. [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.
    連結:
  29. [37] Frank, H., "Optimum locations on a graph with probabilistic demands," Operations Research, vol. 14, 409-421, 1966.
    連結:
  30. [38] Frank, H., "Optimum locations on a graph with correlated normal demands," Operations Research, vol. 14, 552-557, 1967.
    連結:
  31. [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.
    連結:
  32. [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.
    連結:
  33. [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.
    連結:
  34. [43] Goldman, A. J., "Optimal center location in simple networks," Transportation Science, vol. 5, 212-221, 1971.
    連結:
  35. [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.
    連結:
  36. [45] Halpern, J., "The location of a cent-dian convex combination on an undirected tree," Journal of Regional Science, vol. 16, 237-245, 1976.
    連結:
  37. [46] Halpern, J., "Finding minimal center-median convex combination (cent-dian) of a graph," Management Science, vol. 24, no. 5, 535-547, 1978.
    連結:
  38. [47] Halpern, J., "Duality in the cent-dian of a graph," Operations Research, vol. 28, 722-735, 1980.
    連結:
  39. [48] Hsu, W. L., "The distance-domination numbers of trees," Operations Research Letters, vol. 1, 96-100, 1982.
    連結:
  40. [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.
    連結:
  41. [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.
    連結:
  42. [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.
    連結:
  43. [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.
    連結:
  44. [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.
    連結:
  45. [56] Kouvelis, P. and Yu, G., Robust discrete optimization and its applications, Kluwer Academic Publishers, Dordrecht, 1997.
    連結:
  46. [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.
    連結:
  47. [59] Labb□, M., Thisse, J.-F., and Wendell, R., "Sensitivity analysis in minisum facility location problems," Operations Research, vol. 38, 961-969, 1991.
    連結:
  48. [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.
    連結:
  49. [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.
    連結:
  50. [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.
    連結:
  51. [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.
    連結:
  52. [64] Minieka, E., "Anticenters and antimedians of a network," Networks, vol. 13, 359-364, 1983.
    連結:
  53. [66] Mirchandani, P. B. and Odoni, A. R., "Location of medians on stochastic networks," Transportation Science, vol. 13, 85-97, 1979.
    連結:
  54. [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.
    連結:
  55. [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.
    連結:
  56. [69] Nickel, S. and Puerto, J., "A unified approach to network location problems," Networks, vol. 34, 283-290, 1999.
    連結:
  57. [70] Nickel, S. and Puerto, J., Location Theory: A unified approach, Springer-Verlag, Heidelberg, Germany, 2005.
    連結:
  58. [73] P□rez-Brito, D. and Moreno-P□rez, J. A., "The generalized p-centdian on network," Top, vol. 8, no. 2, 265-285, 2000.
    連結:
  59. [74] Puerto, J. and Rodr□guez-Ch□a, A. M., "Robust positioning of service units," Stochastic Models, vol. 19, no. 1, 125-147, 2003.
    連結:
  60. [75] Puerto, J., Rodr□guez-Ch□a, 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.
    連結:
  61. [76] Rodr□guez-Ch□a, A. M., Nickel, S., Puerto, J. and Fern□ndez, F. R., "A flexible approach to location problems," Mathematical Methods of Operations Research, vol. 51, no. 1, 69-89, 2000.
    連結:
  62. [77] Slater, P. J., "Centers to centroids in a graph," Journal of Graph Theory, vol. 2, 209-222, 1978.
    連結:
  63. [78] Synder, L., "Facility location under uncertainty: A review," IIE Transactions, vol. 38, no. 7, 547-564, 2006.
    連結:
  64. [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.
    連結:
  65. [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.
    連結:
  66. [81] Tamir, A., "Obnoxious facility location on graphs," SIAM Journal on Discrete Mathematics, vol. 4, no. 4, 550-567, 1991.
    連結:
  67. [82] Tamir, A., "The k-centrum multi-facility location problem," Discrete Applied Mathematics, vol. 109, 293-307, 2001.
    連結:
  68. [83] Ting, S. S., "A linear time algorithm for maxisum facility location on tree networks," Transportation Science, vol. 18, 76-84, 1984.
    連結:
  69. [84] Tamir, A., P□rez-Brito, D., and Moreno-P□rez, J. A., "A polynomial algorithm for the p-centdian problem on a tree," Networks, vol. 32, 255-262, 1998.
    連結:
  70. [86] Weaver, J. R. and Church, R. L., "Computational procedures of location problems on stochastic networks," Transportation Science, vol. 17, 168-180, 1983.
    連結:
  71. [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.
    連結:
  72. [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.
    連結:
  73. [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.)
  74. [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.
  75. [20] Cappanera P, "A survey on obnoxious facility location problems," Technical Report, TR-99-11, Dipartimento di Informatica, Universita di Pisa, 1999.
  76. [21] Carrizosa, E. J., Conde, E., Fern□ndez, F. R., and Puerto, J., "An axiomatic approach to the cent-dian criterion," Location Science, vol. 3, 1-7, 1994.
  77. [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.
  78. [29] Daskin, M. S., Network and discrete location: models, algorithms, and applications, Wiley, New York, 1995.
  79. [30] Drezner, Z., Facility location. A survey of applications and methods, Springer, New York, 1995.
  80. [32] Drezner, Z. and Hamacher, H. W., Facility location: applications and theory, Springer-Verlag, New York, 2002.
  81. [39] Frederickson, G. N., "Optimal parametric search algorithms in trees II: p-center problems and check points," Technical Report, Purdue University, 1992.
  82. [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.
  83. [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.
  84. [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.
  85. [65] Mirchandani P. B. and Francis R. L., Discrete location theory, Wiley, New York, 1990.
  86. [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.
  87. [72] Oudjit, A., "Median locations on deterministic and probabilistic multidimensional networks," PhD Dissertation, Rennselaer Polytechnic Institute, Troy, 1981.
  88. [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.