Was ist das kürzeste Superstring für $ {c (ab) ^ k, (ba) ^ k, (ab) ^ k c \} $?

Question

in dieses Papier auf PDF Seite 3, sie geben $ \ {c (ab) ^ k, (BA) ^ k, (ab) ^ kc \} $ als Beispiel einer Eingabe für den gierigen Algorithmus für kürzeste Superstring, der dazu führt, dass es ein Annäherungsverhältnis von 2 hat.

Soweit ich erkennen kann, ist der kürzeste Superstring dieses Sets entweder $ C (AB) ^ kc (BA) ^ K $ oder $ B (AB) ^ kc (ab) ^ k $ - Soweit ist die Länge $ 4k + 2 $ . Leider widerspricht dies dem Anspruch in dem Papier, an dem gierig eine Längenkette zweimal das optimale Superstring ausgibt.

.
• ohne Verlust der Allgemeinheit können wir davon ausgehen, dass Gieriger niemals länger länger als die Verkettung seines Eingangssatzes ausgibt - wenn der gierige Algorithmus wirklich auf diese Weise beschrieben wird, können wir einfach eine IF-Anweisung hinzufügen, um diesen Fall zu überprüfen und geben Sie stattdessen die Verkettung zurück.
• Die Länge der Verkettung der Eingangssafen ist 6.000 $ + 2 $ .
• für alle $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4k + 2} \ le 1,5 $
• Daher muss entweder das Annäherungsquote für einen vernünftigen Algorithmus auf dieser Klasse von Problemen weniger als oder gleich 1,5 sein, oder was ich denke, dass der kürzeste Superstring nicht eigentlich der kürzeste ist.

Kann jemand entweder erklären, warum diese Argumentation nicht funktioniert oder sagen, was das eigentliche kürzeste Superstring dieses Sets ist?

Answer 1

Ein kürzerer Superstring ist $ C (AB) ^ {k + 1} C $ , das Länge $ 2k hat+4 $ .