Qual è il più breve superstring per $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ k c \} $?

Question

in Questo documento su PDF Page 3, danno $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ kc \} $ come esempio di un input per l'algoritmo avido per il più breve SuperString che lo causa avere un rapporto di approssimazione di 2.

Per quanto posso dire, la più breve sovrasociazione di quel set è o $ c (ab) ^ kc (BA) ^ k $ o $ B (AB) ^ KC (AB) ^ K $ - In entrambi i casi, la lunghezza è $ 4k + 2 $ . Sfortunatamente, questo contraddice il reclamo nella carta che Greedy emette una stringa di lunghezza 2 volte la superstring ottimale.

.
• Senza perdita di generalità, possiamo supporre che Greedy non produce mai una stringa più lunga della concatenazione del suo set di input - se l'algoritmo avido è davvero descritto in questo modo, possiamo semplicemente aggiungere una dichiarazione se per verificare quella custodia e restituire invece la concatenazione.
• La lunghezza della concatenazione delle stringhe di ingresso è $ 6k + 2 $ .
• per tutto $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4K + 2} \ LE 1.5 $
• Pertanto il rapporto approssimativo per qualsiasi algoritmo ragionevole su questa classe di problemi deve essere inferiore o uguale a 1,5, o quello che penso è il più breve la superstring non è in realtà il più breve.

Qualcuno può o spiegare perché questa riga di argomentazione non funziona, o dire quale sia la sovrasociazione più breve di questo set?

Answer 1

Un superstring più corto è $ c (ab) ^ {k + 1} c $ , che ha lunghezza $ 2K+4 $ .