The Shortest Superstring Problem

Theodoros P. Gevezes () and Leonidas S. Pitsoulis ()
Additional contact information
Theodoros P. Gevezes: Aristotle University of Thessaloniki, Faculty of Engineering, School of Electrical and Computer Engineering
Leonidas S. Pitsoulis: Aristotle University of Thessaloniki, Faculty of Engineering, School of Electrical and Computer Engineering

A chapter in Optimization in Science and Engineering, 2014, pp 189-227 from Springer

Abstract: Abstract The shortest superstring problem (SSP) is a combinatorial optimization problem which has attracted the interest of many researchers due to its applications in computational molecular biology and in computer science. The SSP is an NP-hard problem, and therefore great effort to develop exact algorithms for it has not been made. On the other hand, several approximation and heuristic algorithms have been implemented indicating the strong effectiveness of the greedy strategies to this problem. Variations of these algorithms can be parallelized providing computational strength in solving real-world instances. Polynomially solvable versions of the problem obtained under specific restrictions to its parameters reveal the boundaries between hard and easy cases. The computational bounds on the approximability of the SSP are a realization of its Max-SNP-hardness, but the weak proved values of them reflect the potential strength of the greedy approximation techniques. The strength of the greedy methods for the SSP is enhanced also by the asymptotic behaviour and the smoothed analysis of the problem in random and real-world instances, respectively. All these issues are presented in this chapter in a concise way covering the whole relevant literature, revealing the knowledge that is already conquered, and paving the path for further development in the study of shortest superstrings. The order of the sections highlights the pass from hardness complexity results for the SSP to efficient algorithms for the problem based on greedy strategies, and to theoretical results that establish the strength of the greedy techniques.

Keywords: Approximation Algorithm; Approximation Ratio; Hamiltonian Cycle; Greedy Randomize Adaptive Search Procedure; Hamiltonian Path (search for similar items in EconPapers)
Date: 2014
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4939-0808-0_10

Ordering information: This item can be ordered from
http://www.springer.com/9781493908080

DOI: 10.1007/978-1-4939-0808-0_10

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().