Asymmetric distances,semidirected networks and majority in Fermat–Weber problems |
| |
Authors: | Frank Plastria |
| |
Institution: | (1) MOSI—Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussels, Belgium |
| |
Abstract: | 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. |
| |
Keywords: | Fermat– Weber problem Asymmetric distance Quasimetric Dominance Directed network Semidirected network Node optimality |
本文献已被 SpringerLink 等数据库收录! |
|