Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks
Tóm tắt
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}}\left( p^2 n \log n\right) $$
and
$${{\mathcal {O}}}\left( p^{2}(n \log n+ n \log \eta _{\max })\right) $$
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^2n \log n)$$
time.
Tài liệu tham khảo
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)
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)
Alizadeh, B., Etemad, R.: Linear time optimal approaches for reverse obnoxious center location problems on networks. Optimization 65, 2025–2036 (2016)
Alizadeh, B., Etemad, R.: Optimal algorithms for inverse vertex obnoxious center location problems on graphs. Theor. Comput. Sci. 707, 36–45 (2018)
Cappanera, P., Gallo, G., Maffioli, F.: Discrete facility location and routing of obnoxious activities. Discrete Appl. Math. 133, 3–28 (2003)
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)
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)
Etemad, R., Alizadeh, B.: Reverse selective obnoxious center location problems on tree graphs. Math. Methods Oper. Res. 87, 431–450 (2018)
Galavii, M.: Inverse 1-Median Problems. Ph.D. Thesis, Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz (2008)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of \( {{\rm {N}}}{{\rm {P}}}\)-Completeness. Freeman, San Francisco (1979)
Gassner, E.: The inverse 1-maxian problem with edge length modification. J. Comb. Optim. 16, 50–67 (2008)
Goodrich, M.T., Tamassia, R., Mount, D.: Data Structures and Algorithms in C++. Wiley, New York (2003)
Hochbaum, D.S.: The pseudoflow algorithm: a new algorithm for the maximum flow problem. Oper. Res. 56, 992–1009 (2008)
Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2004)
Nguyen, K.T., Vui, P.T.: The invere \( p \)-maxian problem on trees with variable edge lengths. Taiwan. J. Math. 20, 1437–1449 (2016)
Plastria, F.: Optimal location of undesirable facilities: a selective overview. Belg. J. Oper. Res. Stat. Comput. Sci. 36, 109–127 (1996)
Zanjirani, R., Hekmatfar, M.: Facility Location: Concepts, Models, Algorithms and Case Studies. Physica-Verlag, Berlin (2009)
Zhang, J., Liu, Z., Ma, Z.: Some reverse location problems. Eur. J. Oper. Res. 124, 77–88 (2000)