Improved Approximability Result for Test Set with Small Redundancy
| dc.creator | Cui, Peng | |
| dc.date | 2007-05-17 | |
| dc.date | 2007-09-27 | |
| dc.date.accessioned | 2026-07-07T08:32:11Z | |
| dc.date.available | 2026-07-07T08:32:11Z | |
| dc.description | Test set with redundancy is one of the focuses in recent bioinformatics research. Set cover greedy algorithm (SGA for short) is a commonly used algorithm for test set with redundancy. This paper proves that the approximation ratio of SGA can be $(2-\frac{1}{2r})\ln n+{3/2}\ln r+O(\ln\ln n)$ by using the potential function technique. This result is better than the approximation ratio $2\ln n$ which directly derives from set multicover, when $r=o(\frac{\ln n}{\ln\ln n})$, and is an extension of the approximability results for plain test set. | |
| dc.description | 7 pages | |
| dc.identifier | https://arxiv.org/abs/0705.2503 | |
| dc.identifier | http://arxiv.org/abs/0705.2503 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/138721 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.title | Improved Approximability Result for Test Set with Small Redundancy | |
| dc.type | text |