Abstract
This paper considers the inverse 1-center location problem with edge length augmentation on a tree network T with n + 1 vertices. The goal is to increase the edge lengths at minimum total cost subject to given modification bounds such that a predetermined vertex s becomes an absolute 1-center under the new edge lengths. Using a set of suitably extended AVL-search trees we develop a combinatorial algorithm which solves the inverse 1-center location problem with edge length augmentation in O(n log n) time. Moreover, it is shown that the problem can be solved in O(n) time if all the cost coefficients are equal.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Alizadeh B, Burkard RE (2009) Combinatorial algorithms for inverse absolute and vertex 1-center location problems on trees. Technical Report 2009–09, Graz University of Technology
Balas E, Zemel E (1980) An algorithm for large zero-one knapsack problems. Oper Res 28: 1130–1154
Burkard RE, Pleschiutschnig C, Zhang J (2004) Inverse median problems. Discret Optim 1: 23–39
Burkard RE, Pleschiutschnig C, Zhang J (2007) The inverse 1-median problem on a cycle. Discret Optim 5: 242–253
Cai MC, Yang XG, Zhang JZ (1999) The complexity analysis of the inverese center location problem. J Global Optim 15: 213–218
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge
Daskin MS (1995) Network and discrete location: modeles, algorithms and applications. Wiley, New York
Drezner Z, Hamacher HW (2004) Facility location, applications and theory. Springer, Berlin
Duin CW, Volgenant A (2006) Some inverse optimization problems under the Hamming distance. Eur J Oper Res 170: 887–899
Francis RL, McGinnis LF, White JA (1992) Facility layout and location, an analytical approach. Prentice Hall, Englewood Cliffs
Galavii M (2008) Inverse 1-median problems. Ph.D. Disseration, Graz University of Technology
Gassner E (2007) The inverse 1-maxian problem with edge length modification. J Comb Optim 16: 50–67
Gassner E (2008) An inverse approach to convex ordered median problems in trees. Technical Report 2008–16, Graz University of Technology
Goodrich MT, Tamassia R, Mount D (2003) Data structures and algorithms in C++. Wiley, New York
Guan X, Zhang J (2006) Inverse bottleneck optimization problems on networks. Lect Notes Comput Sci 4041: 220–230
Handler GY (1973) Minimax location of a facility in an undirected tree graph. Transp Sci 7: 287–293
Heuberger C (2004) Inverse combinatorial optimization: a survey on problems, methods, and results. J Comb Optim 8: 329–361
Hatzl J (2006) Personal communication. Graz University of Technology, Graz
Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Berlin
Mirchandani BP, Francis RL (1990) Discrete location theory. Wiley, New York
Nickel S, Puerto J (2005) Location theory, a unified approach. Springer, Berlin
Yang X, Zhang J (2008) Inverse center location problem on a tree. J Syst Sci Complex 21: 51–664
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by R. Weismantel.
B. Alizadeh acknowledges financial support by the NAWI-Project in joint cooperation between Graz University of Technology and Karl-Franzens University of Graz under the grant F-NW-MATH-05. This research has also been supported by the Austrian Science Fund (FWF) Project P18918-N18.
Rights and permissions
About this article
Cite this article
Alizadeh, B., Burkard, R.E. & Pferschy, U. Inverse 1-center location problems with edge length augmentation on trees. Computing 86, 331–343 (2009). https://doi.org/10.1007/s00607-009-0070-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00607-009-0070-7