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_\infty \) norm and bottleneck Hamming distance. We design an \(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}\) ) with time complexity \(O(n^2\log n)\) . Finally, we show some computational experiments to verify the effectiveness of the algorithms.