Qual é o mais curto superstring por $ \ {C (AB) ^ K, (BA) ^ K, (AB) ^ K c} $?

Question

em este artigo no PDF Page 3, eles dão $ \ {c (ab) ^ k, (BA) ^ k, (ab) ^ k} $ como um exemplo de uma entrada para o algoritmo ganancioso para mais curto superstring que faz com que ele tenha uma proporção de aproximação de 2.

Tanto quanto eu posso dizer, o mais curto superstring desse conjunto é $ c (ab) ^ kc (BA) ^ k $ ou $ B (AB) ^ KC (AB) ^ K $ - De qualquer forma, o comprimento é $ 4K + 2 $ . Infelizmente, isso contradiz a reivindicação no papel que ganancioso produz uma seqüência de comprimento 2 vezes a superstring ideal.

• sem perda de generalidade, podemos supor que o ganancioso nunca produzirá uma corda mais longa do que a concatenação de seu conjunto de entrada - se o algoritmo ganancioso realmente é descrito dessa forma, podemos apenas adicionar uma instrução IF para verificar esse caso e devolver a concatenação em vez disso.
• O comprimento da concatenação das cadeias de entrada é $ 6k + 2 $ .
• para todos $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4K + 2} \ le 1,5 $
• , portanto, a proporção de aproximação para qualquer algoritmo razoável nesta classe de problemas deve ser menor ou igual a 1,5, ou o que eu acho que é o menor superstring não é realmente o menor.

Alguém pode explicar por que essa linha de argumentação não funciona ou diga o que é o mais curto mais curto desse conjunto?

Answer 1

Um superstring mais curto é $ c (ab) ^ {k + 1} c $ , que tem comprimento $ 2k+4 $ .