Какое самое короткое заметное для $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ k c \} $?

Question

в Эта статья на PDF Page 3, они дают $ \ {c (ab) ^ k, (ba) ^ k, (ab) ^ kc \} $ в качестве примера входа в жадный алгоритм для кратчайшего Superstring, который приводит к тому, что он имеет отношение приближения 2.

Насколько я могу сказать, кратчайший сверхструйный из этого набора является либо $ C (AB) ^ KC (BA) ^ k $ или $ B (AB) ^ кЦ (ab) ^ k $ - в любом случае, длина - 4k + 2 $ Отказ К сожалению, это противоречит претензию в документе, что жадные выводит строку длиной 2 раза оптимального суперструнда.

.
• без потери общности, мы можем предположить, что жадные никогда не выводят строку дольше, чем конкатенация его входного набора - если жадный алгоритм на самом деле описан таким образом, мы можем просто добавить оператор IF, чтобы проверить этот случай и вместо этого вернуть конкатенацию.
• Длина конкатенации входных строк составляет $ 6k + 2 $ .
• для всех $ k \ in \ mathbb {n} $ , $ 1 \ le \ frac {6k + 2} {4k + 2} \ le 1,5 $
Поэтому либо соотношение аппроксимации для любого разумного алгоритма по этому классу проблем должно быть меньше или равно 1,5, или то, что я думаю, является самым коротким суперструнгом, на самом деле не самый короткий.

Может ли кто-то либо объяснить, почему эта строка аргументации не работает, или говорит, какая фактическая кратчайшая сверхстройка этого набора?

Answer 1

Короче надписи $ c (ab) ^ {k + 1} c $ , который имеет длину $ 2k+4 $ .