Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

Medians of Binary Relations: Computational Complexity.

Please always quote using this URN: urn:nbn:de:0297-zib-746
  • Let $\Re$ be the set of all binary relations on a finite set $N$ and $d$ be the symmetric difference distance defined on $\Re$. For a given profile $\Pi = (R_1,...,R_m) \in R^m$, a relation $R* \in \Re $ that minimizes the function $\sum^m_{k=1} d(R_k,R) $ is called a median relation of $\Pi$. A number of problems occuring in the social sciences, in qualitative data analysis and in multicriteria decision making can be modelled as problems of finding medians of a profile of binary relations. In these contexts the profile $\Pi$ represents collected data (preferences, similarities, games) and the objective is that of finding a median relation of $\Pi$ with some special feature (representing e. g., 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: reflexitivity, symmetry, antisymmetry, transitivity and completeness. We prove that whenever transitivity is required (except when symmetry and completeness are also simultaneously required) then the corresponding median problem is $NP$-hard. In some cases we prove that they remain $NP$-hard when the profile $\Pi$ has a fixed number of binary relations.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Yoshiko Wakabayashi
Document Type:ZIB-Report
Date of first Publication:1992/03/23
Series (Serial Number):ZIB-Report (SC-92-04)
ZIB-Reportnumber:SC-92-04
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.