The Complexity of Computing Medians of Relations
Yoshiko Wakabayashi · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 1998
Let N be a finite set and R be the set of all binary relations on N . Consider R endowed with a metric d, the symmetric difference distance. For a given m-tuple = (R 1 ; : : : ; Rm ) 2 R m , a relation R 2 R that minimizes the function P m k=1 d(R k ; R) is called a median relation of . In the social sciences, in qualitative data analysis and in multicriteria decision making, problems occur in which the m-tuple represents collected data (preferences, similarities, games) and the objective is that of finding a median relation of with some special feature (representing for example, consensus of preferences, clustering of similar objects, ranking of teams, etc.). In this paper we analyse the computational complexity of all such problems in which the median is required to satisfy one or more of the properties: reexitivity, symmetry, antisymmetry, transitivity and completeness. We prove that whenever transitivity is required (except when symmetry and completeness are also si...