Polynomial-time approximation algorithms for weighted LCS problem
| Autor: | Tomasz Waleń, Marek Cygan, Marcin Kubica, Wojciech Rytter, Jakub Radoszewski |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
0301 basic medicine
Discrete mathematics Sequence Applied Mathematics Open problem Approximation algorithm 0102 computer and information sciences Longest increasing subsequence 01 natural sciences Polynomial-time approximation scheme Combinatorics Longest common subsequence problem 03 medical and health sciences 030104 developmental biology 010201 computation theory & mathematics Bounded function Subsequence Discrete Mathematics and Combinatorics Mathematics |
| Zdroj: | Discrete Applied Mathematics. 204:38-48 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2015.11.011 |
| Popis: | We consider a variant of the well-known Longest Common Subsequence (LCS) problem for weighted sequences. A weighted sequence determines the probability for each symbol to occur at a given position of the sequence (such sequences are also called Position Weighted Matrices, PWM). Two possible such versions of the problem were proposed by (Amir et?al., 2009 and 2010), they are called LCWS and LCWS2 (Longest Common Weighted Subsequence 1 and 2). We solve an open problem, stated in the paper by Amir et?al., of the tractability of a log-probability version of LCWS2 problem for bounded alphabets, showing that it is NP-hard already for an alphabet of size 2. We also improve the ( 1 / | Σ | ) -approximation algorithm given by Amir et?al. (where Σ is the alphabet): we show a polynomial-time approximation scheme (PTAS) for the LCWS2 problem using O ( n 5 ) space. We also give a simpler (1/2)-approximation algorithm for the same problem using only O ( n 2 ) space. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect