最短公共超串的多项式时间2-近似算法
A Polynomial-Time 2-Approximation for Shortest Common Superstring
OpenAI 数学仓库收录的研究手稿。展开查看英文摘要，或标记后让我进一步解释。
具体内容
稿件研究最短公共超串问题，目标是为有限个显式表示的普通字符串寻找公共超串。作者声称给出一个确定性算法，在总编码输入规模（包括符号标签）的多项式时间内，输出长度不超过最优解两倍的公共超串。摘要强调该保证适用于所构造的算法，而非经典的最大重叠贪心过程。研究意义在于为最短公共超串提供具有明确近似比的多项式时间算法。
- 针对有限族显式普通字符串构造公共超串。
- 算法为确定性，运行时间关于总编码输入规模多项式。
- 输出长度不超过最优解两倍，且保证不适用于经典贪心过程。
AI 产生的研究手稿；收录不表示已完成独立审查或同行评议。
英文原始摘要
We give a deterministic algorithm that, for every finite family of explicitly represented ordinary strings, outputs a common superstring of length at most twice the optimum in time polynomial in the total encoded input size, including symbol labels. The guarantee applies to the algorithm constructed here, not the classical maximum-overlap Greedy procedure.
用户标记：未标记
固定编号：d99d623c24541ba4
原文来源