This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network. We call this problem as the integer inverse undesirable p-median location model. Exact combinatorial algorithms with $\mathcal{O}({p^2}\;n\;\log \;n)$ and $\mathcal{O}({p^2}(n\;\log \;n + n\;\log \;\eta {}_{\max }))$ running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms, respectively. Furthermore, it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in $\mathcal{O}({p^2}\;n\;\log \;n)$ time.
Esmaeil Afrashteh, Behrooz Alizadeh, Fahimeh Baroughi
. Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks[J]. Journal of the Operations Research Society of China, 2021
, 9(1)
: 99
-117
.
DOI: 10.1007/s40305-018-0229-z
[1] Alizadeh, B., Afrashteh, E., Baroughi, F.:Combinatorial algorithms for some variants of inverse obnoxious p-median location problem on tree networks. J. Optim. Theory Appl. 178, 914-934(2018)
[2] Alizadeh, B., Burkard, R.E.:A linear time algorithm for inverse obnoxious center location problems on networks. Cent. Eur. J. Oper. Res. 21, 585-594(2013)
[3] Alizadeh, B., Etemad, R.:Linear time optimal approaches for reverse obnoxious center location problems on networks. Optimization 65, 2025-2036(2016)
[4] Alizadeh, B., Etemad, R.:Optimal algorithms for inverse vertex obnoxious center location problems on graphs. Theor. Comput. Sci. 707, 36-45(2018)
[5] Cappanera, P., Gallo, G., Maffioli, F.:Discrete facility location and routing of obnoxious activities. Discrete Appl. Math. 133, 3-28(2003)
[6] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.:Introduction to Algorithms. MIT Press, Cambridge (2001)
[7] Etemad, R., Alizadeh, B.:Combinatorial algorithms for reverse selective undesirable center location problems on cycle graphs. J. Oper. Res. Soc. China 5, 347-361(2017)
[8] Etemad, R., Alizadeh, B.:Reverse selective obnoxious center location problems on tree graphs. Math. Methods Oper. Res. 87, 431-450(2018)
[9] Galavii, M.:Inverse 1-Median Problems. Ph.D. Thesis, Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz (2008)
[10] Garey,M.R.,Johnson,D.S.:ComputersandIntractability:AGuidetotheTheoryofNP-Completeness. Freeman, San Francisco (1979)
[11] Gassner, E.:The inverse 1-maxian problem with edge length modification. J. Comb. Optim. 16, 50-67(2008)
[12] Goodrich, M.T., Tamassia, R., Mount, D.:Data Structures and Algorithms in C++. Wiley, New York (2003)
[13] Hochbaum, D.S.:The pseudoflow algorithm:a new algorithm for the maximum flow problem. Oper. Res. 56, 992-1009(2008)
[14] Kellerer, H., Pferschy, U., Pisinger, D.:Knapsack Problems. Springer, Berlin (2004)
[15] Nguyen, K.T., Vui, P.T.:The invere p-maxian problem on trees with variable edge lengths. Taiwan. J. Math. 20, 1437-1449(2016)
[16] Plastria, F.:Optimal location of undesirable facilities:a selective overview. Belg. J. Oper. Res. Stat. Comput. Sci. 36, 109-127(1996)
[17] Zanjirani, R., Hekmatfar, M.:Facility Location:Concepts, Models, Algorithms and Case Studies. Physica-Verlag, Berlin (2009)
[18] Zhang, J., Liu, Z., Ma, Z.:Some reverse location problems. Eur. J. Oper. Res. 124, 77-88(2000)
