论文标题
三胞胎重建和所有其他系统发育CSP都是抗近似值的
Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
论文作者
论文摘要
We study the natural problem of Triplet Reconstruction (also Rooted Triplets Consistency or Triplet Clustering), originally motivated in computational biology and relational databases (Aho, Sagiv, Szymanski, and Ullman, 1981): given $n$ points, we want to embed them onto the $n$ leaves of a rooted binary tree (a hierarchical clustering or ultrametric embedding) such that a given set of满足了$ M $三胞胎约束。 Triplet $ ij | k $表示``$ i，j $彼此之间的关系比$ k $''与$ k $''更紧密相关，并且一棵树满足$ ij | k $，如果$ d（i，j）$是3个距离中最小的。 Aho等。 （1981）给出了一种优雅的有效算法，以找到尊重所有约束的树（如果存在），很容易看出随机二进制树是1/3- approximation。不幸的是，尽管进行了四十年的研究，但尚无更好的近似值。 我们的主要定理（将三重态重建作为一种特殊情况）是近似值的一般硬度，涉及无限域的约束满意度问题（CSP）（变量映射到树的任何$ n $叶子）。具体而言，我们在独特的游戏（Khot，2002年）下证明了三胞胎重建，更普遍地，层次结构上的每个CSP都是抗近似值的（没有比偏见的随机分配更好的多项式时间算法，其渐近性更好）。这解决了许多有趣的子树或超级树的聚合问题的近似性。更广泛地说，我们的结果显着扩展了抗近似值谓词的清单，并且是Guruswami，Hastad，Manokaran，Manokaran，Raghavendra和Charikar（2011）的概括，他们表明订购CSP是抗近似值的。我们分析的主要挑战源于树木具有拓扑结构的事实，这就是决定给定三胞胎对叶子的约束是否满足的原因。
We study the natural problem of Triplet Reconstruction (also Rooted Triplets Consistency or Triplet Clustering), originally motivated in computational biology and relational databases (Aho, Sagiv, Szymanski, and Ullman, 1981): given $n$ points, we want to embed them onto the $n$ leaves of a rooted binary tree (a hierarchical clustering or ultrametric embedding) such that a given set of $m$ triplet constraints is satisfied. Triplet $ij|k$ indicates that ``$i, j$ are more closely related to each other than to $k$'' and a tree satisfies $ij|k$ if $d(i,j)$ is the smallest among the 3 distances. Aho et al. (1981) gave an elegant efficient algorithm to find a tree respecting all constraints (if it exists) and it is easy to see that a random binary tree is a 1/3-approximation. Unfortunately, despite more than four decades of research, no better approximation is known. Our main theorem--which captures Triplet Reconstruction as a special case--is a general hardness of approximation result about Constraint Satisfaction Problems (CSPs) over infinite domains (the variables are mapped to any of the $n$ leaves of a tree). Specifically, we prove, under Unique Games (Khot, 2002), that Triplet Reconstruction and more generally, every CSP over hierarchies is approximation resistant (there is no polynomial-time algorithm that does asymptotically better than a biased random assignment). This settles the approximability for many interesting Subtree or Supertree Aggregation Problems. More broadly, our result significantly extends the list of approximation resistant predicates and is a generalization of Guruswami, Hastad, Manokaran, Raghavendra, and Charikar (2011), who showed that ordering CSPs are approximation resistant. The main challenge in our analyses stems from the fact that trees have topology which is what determines whether a given triplet constraint on the leaves is satisfied or not.
