In this paper, we propose to study the following maximum ordinal consensus problem: Suppose we are given a metric system (M, X), which contains k metrics M = {rho_1,..., rho_k} defined on the same point set X. We aim to find a maximum subset X of X such that all metrics in M are consistent when restricted on the subset X. In particular, our definition of consistency will rely only on the ordering between pairwise distances, and thus we call a consistent subset an ordinal consensus of X w.r.t. M. We will introduce two concepts of consistency in the ordinal sense: a strong one and a weak one. Specifically, a subset X is strongly consistent means that the ordering of their pairwise distances is the same under each of the input metric rho_i from M. The weak consistency, on the other hand, relaxes this exact ordering condition, and intuitively allows us to take the plurality of ordering relation between two pairwise distances. We show in this paper that the maximum consensus problems over both the strong and the weak consistency notions are NP-complete, even when there are only 2 or 3 simple metrics, such as line metrics and ultrametrics. We also develop constant-factor approximation algorithms for the dual version, the minimum inconsistent subset problem of a metric system (M, P), - note that optimizing these two dual problems are equivalent.
Download