¿Cuál es la superversura más corta por $ \ {C (AB) ^ K, (BA) ^ K, (AB) ^ K C \} $?

Question

en este papel en PDF Página 3, dan $ \ {c (ab) ^ k, (ba) ^ k, (AB) ^ kc \} $ $ como un ejemplo de una entrada al algoritmo codicioso para el más corto SuperString que hace que tenga una relación de aproximación de 2.

En la medida en que puedo decir, la superversura más corta de ese set es $ c (ab) ^ kc (ba) ^ k $ o $ b (AB) ^ kc (AB) ^ K $ - de cualquier manera, la longitud es $ 4k + 2 $ . Desafortunadamente, esto contradice la reclamación en el documento que GREEDY emite una cadena de longitud 2 veces la superversura óptima.

• Sin pérdida de generalidad, podemos asumir que la codicia nunca emitirá una cadena más larga que la concatenación de su conjunto de entrada: si el algoritmo codicioso realmente se describe de esa manera, podemos agregar una declaración de IF para verificar ese caso y devolver la concatenación en su lugar.
• La longitud de la concatenación de las cadenas de entrada es $ 6k + 2 $ .
• para todos $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4k + 2} \ le 1.5 $
Por lo tanto, la proporción de aproximación para cualquier algoritmo razonable en esta clase de problemas debe ser menor o igual a 1.5, o lo que creo que es la superversura más corta no es en realidad la más corta.

¿Puede alguien explicar por qué esta línea de argumentación no funciona, o decir cuál es la superversura más corta real de este set?

Answer 1

Una superversura más corta es $ c (ab) ^ {k + 1} C $ , que tiene longitud $ 2k+4 $ .