Email this article 
Open Access
Subscription or Fee Access
Computation of Inverse 1-Center Location Problem on the Weighted Trees
Abstract
Let T be a tree with (1)n vertices and n edges with positive edge weights. The inverse 1-center problem on an edge weighted tree consists in changing edge weights at minimum cost so that a pre-specified vertex becomes the 1-center. In the context of location problems Cai et al. [9] proved that the inverse 1-center location problem with edge length modification on general un-weighted directed graphs is NP-hard, while the underlying center location problem is solvable in polynomial time. Alizadeh et al. [1] have designed an algorithm for inverse 1-center location problem with edge length augmentation on trees in (log)Onn time, using a set of suitably extended AVL-search trees. In [2], Alizadeh et al. have designed a combinatorial algorithm for inverse absolute on trees in 2()On time when topology not allowed and 2()Onr time when topology allowed. In this paper, we present an optimal algorithm to find an inverse 1-center location on the weighted trees with (1)n vertices and n edges, where the edge weights can be changed within certain bounds. The time complexity of our proposed algorithm is ()On, if T is traversed in a depth-first-search manner.
Keywords
References
Alizadeh, B. and Burkard, R. E., Inverse 1-center location problems with edge length augmentation on tree, Computing, 86 (2009) 331-343.
Alizadeh, B. and Burkard, R. E., Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees, Networks, 58 (2011) 190-200.
Burton, D. and Toint, Ph. L., On an instance of the inverse shortest paths problem, Math. Programming, 53 (1992) 45-61.
Burkard, R. E., Pleschiutschnig, C. and Zhang, J., Inverse median problems, Discrete Optimization, 1 (2004) 23-39.
Burkard, R. E., Pleschiutschnig, C. and Zhang, J., The inverse 1-median problem on a cycle, Discrete Optimization, 5 (2008) 242–253.
Burkard, R. E., Galavii, M. and Gassner, E., The inverse Fermat-Weber problem, Technical Report 2008-14, Graz University of Technology, Graz, 2008.
Burkard, R. E., Alizadeh, B., Inverse center location problems, International Symposium on Combinatorial Optimization, 36 (2010) 105-110.
Cai, M. C. and Li, Y. J., Inverse matroid intersection problem, ZOR Math. Meth. Oper. Res. 45 (1997) 235-243.
Cai, M. C., Yang, X. G. and Zhang, J. Z., The complex analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999) 213-218.
Daskin, M. S., Network and discrete location: modeles, algorithms and applications, Wiley, New York, 1995.
Dial, R. B., Minimal-revenue congestion pricing part-I: A fast algorithm for the single-origin case, Transportation Res. Part B, 33 (1999) 189-202.
Drezner, Z., Hamacher, H. W., Facility location, applications and theory, Springer, Berlin, 2004.
Duin, C. W. and Volgenant, A., Some inverse optimization problems under the Hamming distance, European Journal of Operational Research, 170 (2006) 887-899.
Engl, H. W., Hanke, M. and Neubauer, A., Regularization of inverse problems, Kluwer Academic Publishers Group: Dordrecht, 1996.
Francis, R. L., McGinnis, L. F. and White, J. A., Facility layout and location, an analytical approach. Prentice Hall, Englewood Cliffs, 1992.
Gassner, E., The inverse 1-maxian problem with edge length modification, J. Combinatorial Optimization, 16 (2007) 50-67.
Galavi, M., Inverse 1-median problems, Ph. D. thesis, Institue of Optimization and Discrete Mathematics, Graz University of Technology, Graz, 2008.
Gassner, E., An inverse approach to convex ordered median problems in trees, Technical Report 2008-16, Graz University of Technology, Graz, 2008.
Guan, X. and Zhang, J., Inverse bottleneck optimization problems under weighted Hamming Distance, Lecture Notes in Computer Science, 4041 (2006) 220-230.
Handler, G. Y., Minimax location of a facility in an undirected tree graph, Transportation Science, 7 (1973) 287–293.
Heuberger, C., Inverse combinatorial optimization: A survey on problems, methods, and results, Journal of Combinatorial Optimization, 8 (2004) 329-361.
Hochbaum, D. S., The pseudoflow algorithm: A new algorithm for the maximum flow problem, Operations Research, 56 (2008) 992–1009.
Kellerer, H., Pferschy, U. and Pisinger, D., Knapsack problems, Springer, Berlin, 2004.
Marlow, B., Inverse problems, http://www.inverse-problems.com/. Megiddo, N., Linear-time algorithms for linear programming in R3 and related problems, SIAM J. Comput., 12 (1983) 759–776.
Mirchandani, B. P. and Francis, R. L., Discrete location theory, Wiley, New York, 1990.
Moser, T. J., Shortest paths calculation of seismic rays, Geophysics, 56 (1991) 59-67.
Nickel, S., Puerto, J., Location theory, a unified approach, Springer, Berlin, 2005.
Yang, C. and Zhang, J. Z., Two general methods for inverse optimization problems, Appl.Math. Lett. 12 (1999) 69-72.
Yang, X. and Zhang, J., Inverse center location problem on a tree, Journal of Systems Science and Complexity, 21 (2008) 651-664.
Zhang, J. Z. and Liu, Z. H., Calculating some inverse linear programming problems, J. Computational and Applied Mathematics, 72 (1996) 261-273.
Zhang, J. Z. and Ma, Z. F., A network flow method for solving some inverse combinatorial optimization problems, Optimization, 37 (1996) 59-72.
Zhang, J., Liu, Z. and Ma, Z., Some reverse location problems, European Journal of Operational Research, 124 (2000) 77–88.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.