J. Blazewicz, E.K. Burke, M. Kasprzak, A. Kovalev, M.Y. Kovalyov
"On the approximability of the Simplified Partial Digest Problem"
Discrete Applied Mathematics
157 (2009) 3586-3592.
Abstract:
In this paper, we analyse the computational complexity of an optimization
version of the Simplified Partial Digest Problem (SPDP), which is a mathematical
model for DNA mapping based on the results of a simplified partial digest
experiment. We prove that recognizing 46.16% of the elements of the DNA map
in the error-free simplified partial digest experiment is NP-hard in the
strong sense. This implies that the problem of maximizing the number of
correct elements of the DNA map in the error-free simplified partial digest
experiment is pseudopolynomially non-approximable with the approximation
ratio 13/6.
Back to the List of publications
26 Oct 2009