Inverse minimax circle location problem with variable coordinates

Document Type : Original Article


Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran


Traditionally, the minimax circle location problems concern finding a circle $C$ in the plane such that the maximum distance from the given points to the circumference of the circle is minimized. The radius of the circle can be fixed or variable. In this paper we consider the inverse case, that is: a circle $C$ with radius $r_0$ is given and we want to modify the coordinate of existing points with the minimum cost such that the given circle becomes optimal. Mathematical models and some properties of the cases that circle $C$ becomes optimal with comparing to all other circles, and circle $C$ becomes the best circle with comparing to the circles with radius $r_0$ are presented.


Main Subjects

[1] B. Alizadeh, E. Afrashteh, and F. Baroughi, Combinatorial algorithms for some variants of inverse obnoxious median location problem on tree networks, J. Optim. Theory Appl., 178 (2018), pp. 914–934.
[2] B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011), pp. 190–200.
[3] B. Alizadeh, R. E. Burkard, and U. Pferschy, Inverse 1-center location problems with edge length augmentation on trees, Computing, 86 (2009), pp. 331–343.
[4] B. Alizadeh and R. Etemad, Optimal algorithms for inverse vertex obnoxious center location problems on graphs, Theoret. Comput. Sci., 707 (2018), pp. 36–45.
[5] F. Baroughi Bonab, R. E. Burkard, and E. Gassner, Inverse p-median problems with variable edge lengths, Math. Methods Oper. Res., 73 (2011), pp. 263–280.
[6] J. Brimberg, H. Juel, and A. Schobel ¨ , Locating a circle on the plane using the minimax criterion, Studies in Locational Analysis, 17 (2009), pp. 46–60.
[7] , Locating a minisum circle in the plane, Discrete Appl. Math., 157 (2009), pp. 901–912.
[8] R. E. Burkard, M. Galavii, and E. Gassner, The inverse Fermat-Weber problem, European J. Oper. Res., 206 (2010), pp. 11–17.
[9] R. E. Burkard, C. Pleschiutschnig, and J. Zhang, Inverse median problems, Discrete Optim., 1 (2004), pp. 23–39.
[10] , The inverse 1-median problem on a cycle, Discrete Optim., 5 (2008), pp. 242–253.
[11] M. C. Cai, X. G. Yang, and J. Z. Zhang, The complexity analysis of the inverse center location problem, J. Global Optim., 15 (1999), pp. 213–218.
[12] Z. Drezner, S. Steiner, and G. O. Wesolowsky, On the circle closest to a set of points, vol. 29, 2002, pp. 637–650. Special issue: Location analysis.
[13] J. Fathali, A row generation method for the inverse continuous facility location problems, Comput. Ind. Eng., 171 (2022), p. 108482.
[14] M. Galavii, The inverse 1-median problem on a tree and on a path, Electron. Notes Discrete Math., 36 (2010), pp. 1241–1248.
[15] M. Gholami and J. Fathali, Mathematical models for the variable weights version of the inverse minimax circle location problem, J. Math. Model., 9 (2021), pp. 137–144.
[16] , The semi-obnoxious minisum circle location problem with Euclidean norm, Int. J. Nonlinear Anal. Appl., 12 (2021), pp. 669–678.
[17] , The inverse minisum circle location problem, Yugosl. J. Oper. Res., 32 (2022), pp. 153–165.
[18] X. Guan and B. Zhang, Inverse 1-median problem on trees under weighted Hamming distance, J. Global Optim., 54 (2012), pp. 75–82.
[19] M. Labbe, G. Laporte, I. Rodr ´ ´ıguez Mart´ın, and J. J. Salazar Gonzalez ´ , Locating median cycles in networks, European J. Oper. Res., 160 (2005), pp. 457–470.
[20] D. T. Lee and Y. F. Wu, Geometric complexity of some location problems, Algorithmica, 1 (1986), pp. 193– 211.
[21] R. F. Love, J. G. Morris, and G. O. Wesolowsky, Facilities location: Models and Methods, (1988).
[22] M. Nazari and J. Fathali, Inverse and rverse 2-facility location problems with equality measures on a network. accepted 2021, In Press.
[23] , Reverse backup 2-median problem with variable coordinate of vertices, Int. J. Oper. Res. Appl., 15 (2018), pp. 63–88.
[24] M. Nazari, J. Fathali, M. Nazari, and S. m. Varedi Koulaei, Inverse of backup 2-median problems with variable edge lengths and vertex weight on trees and variable coordinates on the plane, J. Oper. Manag., 9 (2018), pp. 115–137.
[25] K. T. Nguyen, Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl., 168 (2016), pp. 944–957.
[26] K. T. Nguyen and A. R. Sepasian, The inverse 1-center problem on trees with variable edge lengths under Chebyshev norm and Hamming distance, J. Comb. Optim., 32 (2016), pp. 872–884.
[27] S. Omidi and J. Fathali, Inverse single facility location problem on a tree with balancing on the distance of server to clients, J. Ind. Manag. Optim., 18 (2022), pp. 1247–1259.
[28] S. Omidi, J. Fathali, and M. Nazari, Inverse and reverse balanced facility location problems with variable edge lengths on trees, Opsearch, 57 (2020), pp. 261–273.
[29] A. R. Sepasian and F. Rahbarnia, An O(n log n) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015), pp. 595–602.