Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant.
Vaggos ChatziafratisKonstantin MakarychevPublished in: FOCS (2023)
Keyphrases
- constraint satisfaction problems
- constraint satisfaction
- constraint propagation
- image reconstruction
- three dimensional
- arc consistency
- closed form
- error bounds
- search space
- hypertree decomposition
- approximation methods
- approximation error
- approximation algorithms
- constraint networks
- compressed sensing
- reconstruction process
- temporal constraints
- constraint programming