Fast algorithms for obnoxious location problems

Recently, the location of obnoxious facilities has gained an increasing
interest. The 1-median problem on a network asks for a vertex minimizing the
sum of weighted shortest path distances from itself to all other vertices.
We allow negative weights as well and treat thus the mixed case of a
facility which is friendly for some and obnoxious to other clients. In
particular, we derive a linear time algorithm in the case when the
underlying network is a cactus.
The obnoxious 1-center problem in a graph G asks for a location on an edge of
the graph such that the minimum weighted distance (we assume here positive
weights!) from this point to a vertex of the graph is as large as possibe.
We design linear time algorithms for the case when G is a path or a star,
thus improving previous results of Tamir (1985). Moreover, we will also show
that the unweighted obnoxious 1-center problem on an arbitrary tree can also
be solved in linear time.