The inverse 1-median problem on a tree with transferring the weight of vertices

Document Type : Research Paper

Authors

1 Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran.

2 Faculty of Mathematical Sciences, Shahrood University of Technology, University Blvd., Shahrood, Iran

3 Department of Management and Accounting, Faculty of Industrial Engineering and Management Sciences, Shahrood University of Technology, Shahrood, Iran.

Abstract

In this paper, we investigate a case of the inverse 1-median problem on a tree by transferring the weights of vertices which has not been raised so far. This problem considers modifying the weights of vertices via transferring weights of the vertices with the minimum cost such that a given vertex of the tree becomes the 1-median with respect to the new weights. A linear programming model is proposed for this problem. The applicability and efficiency of the presented model are shown in numerical examples and a real-life problem dealing with transferring users in a social network.

Keywords

Main Subjects

References

[1] B. Alizadeh, R. E. Burkard and U. Pferschy, Inverse 1-center location problems with edge length augmen-tation on trees, Computing, 86 (2009) 331–343.
[2] B. Alizadeh and R. E. Burkard, Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011) 190–200.
[3] R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, Inverse median problems, Discrete Optim., 1 (2004) 23–39.
[4] R. E. Burkard, C. Pleschiutschnig and J. Z. Zhang, The inverse 1-median problem on a cycle, Discrete Optim., 5 (2008) 242–253.
[5] M. C. Cai, X. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, J. Global Optim., 15 (1999) 213–218.
[6] M. S. Daskin, Network and Discrete Location: Models, Algorithms and Applications, ohn Wiley & Sons, Inc., New York, 1995.
[7] H. A. Eiselt and V. Marianov, Foundations of location analysis, International Series in Operations Research and Management Science, Springer, 2011.
[8] J. Fathali and M. Zaferanieh, The balanced 2-median and 2-maxian problems on a tree, J. Comb. Optim., 45 (2023) 16 pp.
[9] M. Galavii, The inverse 1-median problem on a tree and on a path, Electron. Notes Discret. Math., 36 (2010) 1241–1248.
[10] A. J. Goldman, Optimal center location in simple networks, Transportation Sci., 5 (1971) 212–221.
[11] X. Guan and B. Zhang, Inverse 1-median problem on trees under weighted Hamming distance, J. Global Optim., 54 (2012) 75–82.
[12] S. L. Hakimi, Optimum locations of switching centers and the absolute centers and medians of a graph, Operations Research, 12 (1964) 450–459.
[13] M. Nazari and J. Fathali, Inverse and reverse 2-facility location problems with equality measures on a network, Iran. J. Math. Sci. Inform., 18 (2023) 211–225.
[14] K. T. Nguyen, Inverse 1-median problem on block graphs with variable vertex weights, J. Optim. Theory Appl., 168 (2016) 944–957.
[15] K. T. Nguyen, T. H. Nguyen, H. Nguyen-Thu and T. T. Le, Pham V. H., On some inverse 1-center location problems, Optimization, 68 (2019) 999–1015.
[16] 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) 872–884.
[17] 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) 1247–1259.
[18] S. Omidi, J. Fathali and M. Nazari, Inverse and reverse balanced facility location problems with variable edge lengths on trees, Opsearch, 57 (2020) 261–273.
[19] A. R. Sepasian and F. Rahbarnia, An O(nlogn) algorithm for the Inverse 1-median problem on trees with variable vertex weights and edge reductions, Optimization, 64 (2015) 595–602.
[20] A. Weber, Uber den Standort der Industrial, Tubingen Theory of Location of Industries, University of Chicago Press, (1909).
Transactions on Combinatorics
Volume 13, Issue 4 - Serial Number 4
December 2024
Pages 335-350

Files

History

  • Receive Date: 25 February 2023
  • Revise Date: 05 August 2023
  • Accept Date: 24 August 2023
  • Published Online: 01 December 2024

Share

How to cite

Statistics