Asymmetric distances, semidirected networks and majority in Fermat–Weber problems

The Fermat–Weber problem is considered with distance defined by a quasimetric, an asymmetric and possibly nondefinite generalisation of a metric. In such a situation a distinction has to be made between sources and destinations. We show how the classical result of optimality at a destination or a source with majority weight, valid in a metric space, may be generalized to certain quasimetric spaces. The notion of majority has however to be strengthened to supermajority, defined by way of a measure of the asymmetry of the distance, which should be finite. This extended majority theorem applies to most asymmetric distance measures previously studied in literature, since these have finite asymmetry measure. Perhaps the most important application of quasimetrics arises in semidirected networks, which may contain edges of different (possibly zero) length according to direction, or directed edges. Distance in a semidirected network does not necessarily have finite asymmetry measure. But it is shown that an adapted majority result holds nevertheless in this important context, thanks to an extension of the classical node-optimality result to semidirected networks with constraints. Finally the majority theorem is further extended to Fermat–Weber problems with mixed asymmetric distances. Copyright Springer Science+Business Media, LLC 2009