Hardness and approximation of the asynchronous border minimization problem

DOI10.1016/j.dam.2017.08.025zbMath1383.90032arXiv1011.1202OpenAlexW2763957237MaRDI QIDQ1682885

Fencol C. C. Yung, Alexandru Popa, Prudence W. H. Wong, Cindy Y. Li

Publication date: 6 December 2017

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1011.1202

zbMATH Keywords

approximation algorithmsNP-hardnessborder length minimization

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• NP-completeness of the Hamming salesman problem
• A faster algorithm computing string edit distances
• The shortest common supersequence problem over binary alphabet is NP- complete
• Efficient methods for multiple sequence alignment with guaranteed error bounds
• Approximation algorithms for multiple sequence alignment
• ON THE HARDNESS OF THE BORDER LENGTH MINIMIZATION PROBLEM ON A RECTANGULAR ARRAY
• A linear space algorithm for computing maximal common subsequences
• A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
• A tight bound on approximating arbitrary metrics by tree metrics
• The complexity of multiple sequence alignment with SP-score that is a metric

This page was built for publication: Hardness and approximation of the asynchronous border minimization problem