Optimal Algorithms for Integer Inverse Undesirable p-Median Location Problems on Weighted Extended Star Networks  

作　　者：Esmaeil Afrashteh Behrooz Alizadeh Fahimeh Baroughi 

机构地区：[1]Department of Applied Mathematics,Faculty of Basic Sciences,Sahand University of Technology,Tabriz,Iran

出　　处：《Journal of the Operations Research Society of China》2021年第1期99-117,共19页中国运筹学会会刊（英文）

摘　　要：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.

关 键 词：Undesirable p-median location Combinatorial optimization Inverse optimization Time complexity 

分 类 号：O24[理学—计算数学]