$ \ {c（ab）^ k、（ba）^ k、（ab）^ k c} $のための最短スーパーストリングは何ですか？

Question

PDFのPage 3では、彼らは与える $ \ {c（ab）^ k、（ba）^ k、（ba）^ k、（ab）^ kc \} $ 最短のための欲張りアルゴリズムへの入力の例としてそれが2の近似比率を持つようにするスーパースリング。

私が知ることができる限り、そのセットの最短のスーパーストリングは $ c（ab）^ kc（ba）^ k $ または $ B（ab）^ kc（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 $ 。