The tolerant Condorcet points (Q2708114)

The paper contains results of investigation concerning facility location on an undirected network. The facilities can be located not only at vertices but even on edges of the network. The attention is paid to set of points which are acceptable for the majority of users placed at vertices of the network. The term of acceptance is derived from distance between user and possible facility location. The statement ``a point is accepted by the majority of users'' means that for any other location must hold that set of users, which have smaller distance to the location than to the point, does not consist of more then half of all users. The point with the above property is called Condorcet point. In this paper the Condorcet point definition was generalized to alpha-Condorcet point. The alpha-Condorcet point definition is based on tolerance distance alpha, when a user prefers one location to other only if the distances between the user and the locations differ by more then the tolerance distance. Using the alpha-Condorcet property, the term of tolerant Condorcet point is defined here. The tolerant Condorcet point set is alpha-Condorcet point set with the smallest distance alpha, which ensures existence of at least one alpha-Condorcet point. The authors revealed properties of the sets formed by all Condorcet, alpha-Condorcet and tolerant Condorcet points. NEWLINENEWLINENEWLINEThe main goal of the paper is suggestion of an algorithm, which finds the set of all alpha-Condorcet points on a given network for given distance alpha. The algorithm is based on a thoroughful comparison of both member of each pair, which is formed from relevant objects of the network. The pairs consist of two vertices or of vertex and edge or of two edges. During the searching process, every examined edge is splitted into finite set of subedges, where all points of one subedge have uniform relation to the other relevant objects of the network. The authors proved that the algorithm works in polynomial time and they provided the other algorithm, based on dichotomous search, which finds set of tolerant Condorcet points also in polynomial time.