𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The approximability of the String Barcoding problem

✍ Scribed by Giuseppe Lancia, Romeo Rizzi

Book ID
120696644
Publisher
BioMed Central
Year
2006
Tongue
English
Weight
234 KB
Volume
1
Category
Article
ISSN
1748-7188

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Approximability of the Firefighter Probl
Approximability of the Firefighter Problem
✍ Elliot Anshelevich; Deeparnab Chakrabarty; Ameya Hate; Chaitanya Swamy πŸ“‚ Article πŸ“… 2010 πŸ› Springer 🌐 English βš– 600 KB
Approximability of the k-server disconne
Approximability of the k-server disconnection problem
✍ Sung-Pil Hong; Byung-Cheon Choi πŸ“‚ Article πŸ“… 2007 πŸ› John Wiley and Sons 🌐 English βš– 332 KB

## Abstract Consider a network of __k__ servers and their users. Each server provides a unique service that has a certain utility for each user. Now comes an attacker who wishes to destroy a set of network edges to maximize his net gain, namely the total disconnected utilities of the users minus th

On the approximability of the Steiner tr
On the approximability of the Steiner tree problem
✍ Martin Thimm πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 165 KB

We show that it is not possible to approximate the minimum Steiner tree problem within 1 + 1 162 unless RP = NP. The currently best known lower bound is 1 + 1 400 . The reduction is from H astad's nonapproximability result for maximum satisΓΏability of linear equation modulo 2. The improvement on the