Premium
Location of an obnoxious facility on a network: A voting approach
Author(s) -
Labbé Martine
Publication year - 1990
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230200206
Subject(s) - condorcet method , mathematics , point (geometry) , facility location problem , combinatorics , finite set , set (abstract data type) , voting , 1 center problem , upper and lower bounds , mathematical optimization , computer science , mathematical analysis , geometry , politics , political science , law , programming language
We consider the location problem of an obnoxious facility with respect to a finite number of inhabitants, where the inhabitants have specified locations at vertices of a network N . A voting solution, called anti‐Condorcet point, is defined as a point of N such that no other point is farther from a strict majority of inhabitants. On a general network with an odd number of inhabitants, it is shown that there exists a finite set of points that contains all such solutions. An example shows that this result does not directly extend to an even number of inhabitants on a general network. In the special case of a tree network, one of the extreme vertices of a diameter is an anti‐Condorcet point, and a linear algorithm for finding it is presented. Finally, a bound on the maximum decrease of the total distance to the inhabitants is provided when an anti‐Condorcet point is preferred to a “maxisum” location.