English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study the natural problem of Triplet Reconstruction (also Rooted TripletsConsistency or Triplet Clustering), originally motivated in computationalbiology and relational databases (Aho, Sagiv, Szymanski, and Ullman, 1981):given $n$ points, we want to embed them onto the $n$ leaves of a rooted binarytree (a hierarchical clustering or ultrametric embedding) such that a given setof $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 a1/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--isa general hardness of approximation result about Constraint SatisfactionProblems (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 isapproximation resistant (there is no polynomial-time algorithm that doesasymptotically better than a biased random assignment). This settles theapproximability for many interesting Subtree or Supertree Aggregation Problems.More broadly, our result significantly extends the list of approximationresistant predicates and is a generalization of Guruswami, Hastad, Manokaran,Raghavendra, and Charikar (2011), who showed that ordering CSPs areapproximation resistant. The main challenge in our analyses stems from the factthat trees have topology which is what determines whether a given tripletconstraint on the leaves is satisfied or not.

Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant