Inverse Vertex Obnoxious 1-Center Location Problems

In this chapter, we first give a brief introduction to the inverse center and median location problems under different norms. Then we mainly consider the inverse vertex obnoxious 1-center location problem (IVO1C) on a general graph G. We aim to adjust the edge weights satisfying upper and lower bounds with the least cost, so that a given vertex s becomes the obnoxious 1-center of graph G. We construct their mathematical models and prove some properties under the weighted l ∞ $$l_\infty $$ norm and bottleneck Hamming distance. We design an O ( n 3 ) $$O(n^3)$$ time algorithm to solve the problem (IVO1C ∞ $$_\infty $$ ) by solving the transcendence point of the cost function in each iteration, where n is the number of vertices in the graph G. We also propose a binary search method for the problem (IVO1C bH $$_{bH}$$ ) with time complexity O ( n 2 log n ) $$O(n^2\log n)$$ . Finally, we show some computational experiments to verify the effectiveness of the algorithms.