An antimedian of a pro le = (x1; x2; : : : ; xk) of vertices of a graph G is a
vertex maximizing the sum of the distances to the elements of the pro le. The
antimedian function is de ned on the set of all pro les on G and has as output
the set of antimedians of a pro le. It is a typical location function for nding a
location for an obnoxious facility. The `converse' of the antimedian function is the
median function, where the distance sum is minimized. The median function is
well studied. For instance it has been characterized axiomatically by three simple
axioms on median graphs. The median function behaves nicely on many classes
of graphs. In contrast the antimedian function does not have a nice behavior on
most classes. So a nice axiomatic characterization may not be expected. In this
paper such a characterization is obtained for the two classes of graphs on which
the antimedian is well-behaved: paths and hypercubes.
Kannan, Balakrishnan; Manoj, Changat; Henry, Martyn Mulder(Econometric Institute Research Papers, September 15, 2006)
[+]
[-]
Abstract:
The Majority Strategy for finding medians of a set of clients on a graph
can be relaxed in the following way: if we are at v, then we move to a neighbor
w if there are at least as many clients closer to w than to v (thus ignoring the
clients at equal distance from v and w). The graphs on which this Plurality
Strategy always finds the set of all medians are precisely those for which the
set of medians induces always a connected subgraph
Description:
Report/Econometric Institute, Erasmus University Rotterdam