The Effects of Majority in Fermat-Weber Problems With Attraction and Repulsion in a Pseudometric Space


Frank Plastria




The well-known majority theorem for Fermat-Weber location problems states that when all distances are measured by a fixed pseudometric, then any destination with weight at least half of the total weight of all destinations is an optimal site. In this paper we study the implications of such majority when both attracting (positive weight) and repelling (negative weight) destinations are present. When no constraints are present, and when majority holds at an attracting destination, the classical majority theorem is still valid, while when there is a repelling strict majority in an unbounded space, the objective is unbounded below. We then consider the constrained case where the location is restricted to lie within a given compact region. When majority is at an attracting destination then an optimal solution exists which is "first-reachable" from this destination, a generalization of visibility to general pseudometric spaces. When majority is at a repelling destination an optimal solution exists which is "last reachable" from this destination.