Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees |
| |
Authors: | Behrooz Alizadeh Rainer E Burkard |
| |
Institution: | a Graz University of Technology, Institute of Optimization and Discrete Mathematics, Steyrergasse 30, 8010 Graz, Austriab Sahand University of Technology, Faculty of Basic Sciences for Engineering, Department of Applied Mathematics, Tabriz, Iran |
| |
Abstract: | This article considers the inverse absolute and the inverse vertex 1-center location problems with uniform cost coefficients on a tree network T with n+1 vertices. The aim is to change (increase or reduce) the edge lengths at minimum total cost with respect to given modification bounds such that a prespecified vertex s becomes an absolute (or a vertex) 1-center under the new edge lengths. First an O(nlogn) time method for solving the height balancing problem with uniform costs is described. In this problem the height of two given rooted trees is equalized by decreasing the height of one tree and increasing the height of the second rooted tree at minimum cost. Using this result a combinatorial O(nlogn) time algorithm is designed for the uniform-cost inverse absolute 1-center location problem on tree T. Finally, the uniform-cost inverse vertex 1-center location problem on T is investigated. It is shown that the problem can be solved in O(nlogn) time if all modified edge lengths remain positive. Dropping this condition, the general model can be solved in O(rvnlogn) time where the parameter rv is bounded by ⌈n/2⌉. This corrects an earlier result of Yang and Zhang. |
| |
Keywords: | Facility location problem Inverse optimization Combinatorial optimization Absolute and vertex 1-centers |
本文献已被 ScienceDirect 等数据库收录! |