摘要
This paper is concerned with the problem of modifying the edge lengths of a weighted extended star network with n vertices by integer amounts at the minimum total cost subject to be given modification bounds so that a set of p prespecified vertices becomes an undesirable p-median location on the perturbed network.We call this problem as the integer inverse undesirable p-median location model.Exact combinatorial algorithms with O(p2n logn)and O(p2(n logn+n log nmax))running times are proposed for solving the problem under the weighted rectilinear and weighted Chebyshev norms,respectively.Furthermore,it is shown that the problem under the weighted sum-type Hamming distance with uniform modification bounds can be solved in O(p-n log n)time.
