On the Greedy Superstring Conjecture
| Autor: | Maik Weinard, Georg Schnitger |
|---|---|
| Rok vydání: | 2006 |
| Předmět: | |
| Zdroj: | SIAM Journal on Discrete Mathematics. 20:502-522 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/040619144 |
| Popis: | We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring and an optimal cycle cover, provided the greedy algorithm happens to merge the strings in a particular way. Thus, when restricting inputs correspondingly, we verify the well-known greedy conjecture, namely, that the approximation ratio of the greedy algorithm is within a factor of two of the optimum, and actually extend the conjecture considerably. We achieve this bound by systematically combining known conditional inequalities about overlaps and period- and string-lengths with a new familiy of string inequalities. We show that conventional systems of conditional inequalities, including the Monge inequalities, are insufficient to obtain our result. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|