All Instantiations of the Greedy Algorithm for the Shortest Common Superstring Problem are Equivalent

Autor:	Maksim S. Nikolaev
Rok vydání:	2021
Předmět:	Set (abstract data type) Combinatorics Constant factor High Energy Physics::Theory Shortest common superstring Superstring theory Greedy algorithm Mathematics Merge (linguistics)
Zdroj:	String Processing and Information Retrieval ISBN: 9783030866914 SPIRE
DOI:	10.1007/978-3-030-86692-1_6
Popis:	In the Shortest Common Superstring problem (SCS), one needs to find the shortest superstring for a set of strings. While SCS is NP-hard and MAX-SNP-hard, the Greedy Algorithm “choose two strings with the largest overlap; merge them; repeat” achieves a constant factor approximation that is known to be at most 3.5 and conjectured to be equal to 2. The Greedy Algorithm is not deterministic, so its instantiations with different tie-breaking rules may have different approximation factors. In this paper, we show that it is not the case: all factors are equal. To prove this, we show how to transform a set of strings so that all overlaps are different whereas their ratios stay roughly the same.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::aaaac9fb8fe32e9f05efbb9fe022c264 https://doi.org/10.1007/978-3-030-86692-1_6 Zobrazit plný text záznamu