An axiomatization of the median procedure on the n-cube

作者：Mulder Henry Martyn; Novick Beth^*

来源：Discrete Applied Mathematics, 2011, 159(9): 939-944.

DOI：10.1016/j.dam.2011.02.001

• Median
• Median function
• Hypercube
• Location function
• Consensus axiom

The general problem in location theory deals with functions that find sites to minimize some cost, or maximize some benefit, to a given set of clients. In the discrete case sites and clients are represented by vertices of a graph, in the continuous case by points of a network. The axiomatic approach seeks to uniquely distinguish certain specific location functions among all the arbitrary functions that address this problem by using a list of intuitively pleasing axioms. The median function minimizes the sum of the distances to the client locations. This function satisfies three simple and natural axioms: anonymity, betweenness, and consistency. They suffice on tree networks (continuous case) as shown by Vohra (1996) [19], and on cube-free median graphs (discrete case) as shown by McMorris et al. (1998) [9]. In the latter paper, in the case of arbitrary median graphs, a fourth axiom was added to characterize the median function. In this note we show that the above three natural axioms still suffice for the hypercubes, a special instance of arbitrary median graphs.

• 出版日期2011-6-6