Abstract
Given a set of strings S = {s 1,..., s n }, the Shortest Superstring problem asks for the shortest string s which contains each s i as a substring. We consider two measures of success in this problem: the length measure, which is the length of s, and the compression measure, which is the difference between the sum of lengths of the s i and the length of s. Both the length and the compression versions of the problem are known to be MAX-SNP-hard. The only explicit approximation ratio lower bounds are by Ott: 1.000057 for the length measure and 1.000089 for the compression measure. Using a natural construction we improve these lower bounds to 1.00082 for the length measure and 1.00093 for the compression measure. Our lower bounds hold even for instances in which the strings are over a binary alphabet and have equal lengths. In fact, we show a somewhat surprising result, that the Shortest Superstring problem (with respect to both measures) is as hard to approximate on instances over a binary alphabet, as it is over any alphabet.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Armen, C., Stein, C.: Short Superstrings and the Structure of Overlapping Strings. J. Comput. Biol. 2(2), 307–332 (1995)
Berman, P., Karpinski, M.: On some tighter inapproximability results. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 200–209. Springer, Heidelberg (1999)
Bläser, M.: An 8/13–Approximation Algorithm for the Asymmetric Maximum TSP. In: SODA, pp. 64–73 (2002)
Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear Approximation of Shortest Superstrings. In: STOC, pp. 328–336 (1991)
Breslauer, D., Jiang, T., Jiang, Z.: Rotations of Periodic Strings and Short Superstrings. J. Algorithms. 24(2), 340–353 (1997)
Jiang, T., Li, M.: On the Approximation of Shortest Common Supersequences and Longest Common Subsequences. SIAM J. Comput. 24(5), 1122–1139 (1995)
Maier, D., Storer, J.A.: A Note on the Complexity of the Superstring Problem. Princeton University Technical Report 233, Department of Electrical Engineering and Computer Science (1977)
Karpinski, M.: Approximating bounded degree instances of NP-hard problems. In: Freivalds, R. (ed.) FCT 2001. LNCS, vol. 2138, pp. 24–34. Springer, Heidelberg (2001)
Kaplan, H., Shafrir, N.: The Greedy Algorithm for Shortest Superstrings. Information Processing Letters 93, 13–17 (2005)
Middendorf, M.: More on the Complexity of Common Superstring and Supersequence Problems. Theoretical Computer Science 125(2), 205–228 (1994)
Middendorf, M.: On Finding Various Minimal, Maximal, and Consistent Sequences over a Binary Alphabet. Theoretical Computer Science 145, 317–327 (1995)
Ott, S.: Lower Bounds for Approximating Shortest Superstrings over an Alphabet of Size 2. WG, pp. 55–64 (1999)
Sweedyk, Z.: A \(2\frac{1}{2}\)–Approximation Algorithm for Shortest Superstring. SIAM J. Comput. 29(3), 954–986 (1999)
Tarhio, J., Ukkonen, E.: A Greedy Approximation Algorithm for Constructing Shortest Common Superstrings. Theoretical Computer Science 57, 131–145 (1988)
Turner, J.S.: Approximation Algorithms for the Shortest Common Superstring Problem. Information and Computation 83, 1–20 (1989)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vassilevska, V. (2005). Explicit Inapproximability Bounds for the Shortest Superstring Problem. In: Jȩdrzejowicz, J., Szepietowski, A. (eds) Mathematical Foundations of Computer Science 2005. MFCS 2005. Lecture Notes in Computer Science, vol 3618. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11549345_68
Download citation
DOI: https://doi.org/10.1007/11549345_68
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28702-5
Online ISBN: 978-3-540-31867-5
eBook Packages: Computer ScienceComputer Science (R0)