$ \ {c（ab）^ k，（ba）^ k，（ab）^ k c} $什么是最短的超级测试？

Question

在本文在PDF第3页，他们给了 $ \ {c（ab）^ k，（ba）^ k，（ab）^ kc \} $ 作为最短贪婪算法的输入的示例超值导致它具有2的近似率。

据我所知，该集合的最短超级值为 $ c（ab）^ kc（ba）^ $ 或 $ b（ab）^ kc（ab）^ k $ $ - 无论哪种方式，长度为 $ 4k + 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 $ 。