论文标题
在多个指标上的直接共识子集
Ordinally Consensus Subset over Multiple Metrics
论文作者
论文摘要
在本文中，我们建议研究以下最大的顺序共识问题：假设我们获得了一个指标系统（M，X），其中包含K指标M = {ρ_1，...，...，ρ_K}在同一点集X上定义。我们旨在在X上找到最大的子集X'，以便在M中找到“一致的Mentrics”。特别是，我们对一致性的定义仅依赖于成对距离之间的排序，因此我们将“一致”子集称为X W.R.T.的序数共识。 M.我们将在有序意义上介绍两个“一致性”的概念：一个强大的概念和一个弱者。具体而言，子集X'非常一致地意味着，在每个输入度量ρ_i下，它们的成对距离的排序是相同的。另一方面，弱的一致性是放松这种精确排序条件的，并且直觉使我们能够在两个成对距离之间进行多个订购关系。 我们在本文中表明，即使只有2或3个简单的指标，例如线指标和超量表，即使只有2或3个简单的指标，也是NP完整概念的最大共识问题是NP填充的。我们还为双重版本开发了恒定因素近似算法，即公制系统（M，P）的最小不一致的子集问题， - 请注意，优化这两个双重问题是等效的。
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 = {ρ_1,..., ρ_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 ρ_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.
