Abstract

This paper concerns the problem of modifying edge lengths of a network at minimum total costs so as to make a prespecified vertex become an optimal location in the modified environment. Here, we focus on the ordered median objective function with respect to the vector of multipliers λ=(1,…,1,0,…,0) with k 1's. This problem is called the inverse anti-k-centrum problem. We first show that the inverse anti-k-centrum problem is NP-hard even on tree networks. However, for the inverse anti-k-centrum problem on cycles, we formulate it as one or two linear programs, depending on odd or even integer k. Concerning the special cases with k=2,3,M, we develop combinatorial algorithms that efficiently solve the problem, where M is the number of vertices of the cycle.