We investigate the obnoxious facility location problem.
•
The obnoxious facility location problem is equivalent to the -maxian problem.
•
We present an algorithm for the 2-maxian problem on a cactus graph.
Abstract
This paper deals with the 2-maxian problem on cactus graphs. It is shown that in the worst case the midpoint of any path connecting and , where is the 2-maxian of the cactus, lies on a specified cycle. Based on this property, we develop an algorithm with time complexity of for the problem on a cactus with vertices.
This research was partially supported by the National Nature Science Foundation of China (Nos. 10971131, 11171207) and the Major Research Plan of the National Natural Science Foundation of China (Grant No. 91130032).