TY - GEN A1 - Wakabayashi, Yoshiko T1 - Medians of Binary Relations: Computational Complexity. N2 - 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. T3 - ZIB-Report - SC-92-04 Y1 - 1992 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-746 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - A cutting plane algorithm for a clustering problem JF - Mathematical Programming, Series B Y1 - 1989 VL - 45 SP - 59 EP - 96 PB - Mathematical Programming, Series B ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - Facets of the clique partitioning polytope JF - Mathematical Programming, Series A Y1 - 1990 VL - 47 IS - 3 SP - 367 EP - 387 ER - TY - CHAP A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko ED - Bodendiek, Rainer ED - Henn, Rudolf T1 - Composition of facets of the clique partitioning polytope T2 - Topics in combinatorics and graph theory. Essays in honour of Gerhard Ringel Y1 - 1990 SP - 271 EP - 284 PB - Physica-Verlag CY - Heidelberg ER - TY - CHAP A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko ED - Cottle, Richard ED - Kelmanson, Milton ED - Korte, Bernhard T1 - Constructions of hypotraceable digraphs T2 - Mathematical Programming. Proceedings of the International Congress on Mathematical Programming, Rio de Janeiro, Brazil, 6-8 April 1981 Y1 - 1984 SP - 147 EP - 175 PB - North-Holland ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - On the structure of the monotone asymmetric travelling salesman polytope I JF - Discrete Mathematics Y1 - 1981 VL - 34 SP - 43 EP - 59 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - On the structure of the monotone asymmetric travelling salesman polytope II JF - Mathematical Programming Study Y1 - 1981 VL - 14 SP - 77 EP - 97 ER - TY - JOUR A1 - Grötschel, Martin A1 - Thomassen, Carsten A1 - Wakabayashi, Yoshiko T1 - Hypotraceable digraphs JF - Journal of Graph Theory Y1 - 1980 VL - 4 SP - 377 EP - 381 ER - TY - JOUR A1 - Grötschel, Martin A1 - Wakabayashi, Yoshiko T1 - Hypohamiltonian digraphs JF - Methods of Operations Research Y1 - 1980 VL - 36 SP - 99 EP - 119 ER -