Problema de la supercuerda más corta | Conjunto 2 (Usando Set Cover)

Dado un conjunto de n strings S, encuentre la string más pequeña que contiene cada string en el conjunto dado como substring. Podemos suponer que ninguna string en arr[] es una substring de otra string.

Ejemplos:

Input:  S = {"001", "01101", "010"}
Output: 0011010  

Input:  S = {"geeks", "quiz", "for"}
Output: geeksquizfor

Input:  S = {"catg", "ctaagt", "gcta", "ttca", "atgcatc"}
Output: gctaagttcatgcatc

En la publicación anterior , hemos discutido una solución que se demuestra que es 4 aproximada (conjeturada como 2 aproximada).
En esta publicación, se discute una solución que se puede probar como 2H _n aproximada. donde Hn ₌ 1 + 1/2 + 1/3 + … 1/n. La idea es transformar el problema de la supercuerda más corta en un problema de cobertura de conjunto (el problema de cobertura de conjunto tiene algunos subconjuntos de un universo y cada subconjunto dado tiene un costo asociado. La tarea es encontrar el conjunto de menor costo de subconjuntos dados de modo que todos los elementos de universo están cubiertos). Para un problema de Set Cover, necesitamos tener un universo y subconjuntos de universo con sus costos asociados.

A continuación se muestran los pasos para transformar Shortest Superstring en Set Cover .

1) Let S be the set of given strings.
   S = {s1, s2, ... sn}

2) Universe for Set Cover problem is S (We need
   to find a superstring that has every string
   as substring)

3) Let us initialize subsets to be considered for universe as
     Subsets =  {{s1}, {s2}, ... {sn}}
   Cost of every subset is length of string in it.

3) For all pairs of strings si and sj in S,
     If si and sj overlap
      a) Construct a string rijk where k is
         the maximum overlap between the two.
      b) Add the set represented by rijk to Subsets,
           i.e., Subsets = Subsets U Set(rijk)
         The set represented by rijk is the set 
         of all strings which are substring of it.
         Cost of the subset is length of rijk.

4) Now problem is transformed to Set Cover, we can 
   run Greedy Set Cover approximate algorithm to find
   set cover of S using Subsets.  Cost of every element in
   Subsets is length of string in it.

Ejemplo:

S = {s1, s2, s3}.
s1 = "001"
s2 = "01101"
s3 = "010"

[Combination of s1 and s2 with 2 overlapping characters]
r122 = 001101 

[Combination of s1 and s3 with 2 overlapping characters]
r132 = 0010 

Similarly,
r232 = 011010
r311 = 01001
r321 = 0101101

Now set cover problem becomes as following:

Universe to cover is {s1, s2, s3}

Subsets of the universe and their costs :

{s1}, cost 3 (length of s1)
{s2}, cost 5 (length of s2)
{s3}, cost 5 (length of s3)

set(r122), cost 6 (length of r122)
The set r122 represents all strings which are
substrings of r122. 
Therefore set(r122) = {s1, s2}

set(r132), cost 3 (length of r132)
The subset r132 represents all strings which are
substrings of r132
Therefore set(r132) = {s1, s3}

Similarly there are more subsets for set(r232), 
set(r311), and set(r321).

So we have a set cover problem with universe and subsets
of universe with costs associated with every subset.

Hemos discutido que una instancia del problema de Superstring más corta se puede transformar en una instancia del problema Set Cover en tiempo polinomial.

Consulte esto como prueba del hecho de que el algoritmo basado en Set Cover es 2H _n aproximado.

Referencia:
http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/wan-ba-notes.pdf
http://fileadmin.cs.lth.se/cs/Personal/Andrzej_Lingas/ superstring.pdf
http://math.mit.edu/~goemans/18434S06/superstring-lele.pdf

Este artículo es aportado por Dheeraj Gupta . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.