Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2

摘要

The shortest common superstring problme (SCS) is known to be NP-hard and APX-hard. The APX-hardness was proved for the SCS in [BJLTY94], but the reduction used in that paper produces instances with arbitrarily large alphabets. We show that the problem is APX-hard even if the size of the alphabet is 2.