Approximating Shortest Superstrings with Constraints (Extended Abstract)

摘要: Various versions of the shortest common superstring problem play important roles in data compression and DNA sequencing. Only recently, open how to approximate a given set strings was solved [1, 9]. [1] shows that several greedy algorithms produce supeistring length O(n), where n is optimal length. However, major remains open: Can we still linearly polynomial time when required be consistent with some negative strings, i.e., it must not contain any string. The best previous algorithm, Group-Merge [6, 9], produces θ(n log n. make much more difficult and, as will show, greedy-style algorithm cannot achieve linear approximation for this problem.