Explicit Inapproximability Bounds for the Shortest Superstring Problem

摘要: Given a set of strings S = {s1,..., sn}, the Shortest Superstring problem asks for shortest string s which contains each si as substring. We consider two measures success in this problem: length measure, is s, and compression difference between sum lengths s. Both versions are known to be MAX-SNP-hard. The only explicit approximation ratio lower bounds by Ott: 1.000057 measure 1.000089 measure. Using natural construction we improve these 1.00082 1.00093 Our hold even instances over binary alphabet have equal lengths. In fact, show somewhat surprising result, that (with respect both measures) hard approximate on alphabet, it any alphabet.