Given a finite set X and a collection C = (R1, R2, ..., Rm) of m binary relations defined on X and given a remoteness r, a relation R is said to be a median relation of C with respect to r if it minimizes the remoteness r(C, R) from C. The remoteness r is based on the symmetric difference distance d(Ri, R) between R and the binary relations Ri of C (1 <= i <= m), which measures the number of disagreements between Ri and R. Usually, the considered remoteness between C and a relation R is the remoteness r1(C, R) given by the sum of the distances d(Ri, R) over i, and thus measures the total number of disagreements between C and R or, divided by m, provides the (arithmetical) mean number of disagreements between C and R. The computation of a median relation with respect to r1 is often an NP-hard problem when the median relation is required to fulfil structural properties like transitivity. In this paper, we investigate other types of remoteness r, for instance the sum of the pth power of the d(Ri, R)’s for any integer p, the maximum of the d(Ri, R)’s, the minimum of the d(Ri, R)’s, and different kinds of means of the d(Ri, R)’s, or their weighted versions. We show that for many definitions of the remoteness, including the previous ones, the computation of a median relation with respect to r remains NP-hard, even when the number m of relations is given, for any value of m greater than or equal to 1.