English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the Shortest Common Superstring problem (SCS), one needs to find theshortest superstring for a set of strings. While SCS is NP-hard andMAX-SNP-hard, the Greedy Algorithm "choose two strings with the largestoverlap; merge them; repeat" achieves a constant factor approximation that isknown to be at most 3.5 and conjectured to be equal to 2. The Greedy Algorithmis not deterministic, so its instantiations with different tie-breaking rulesmay have different approximation factors. In this paper, we show that it is notthe case: all factors are equal. To prove this, we show how to transform a setof strings so that all overlaps are different whereas their ratios stay roughlythe same.  We also reveal connections between the original version of SCS and thefollowing one: find a~superstring minimizing the number of occurrences of agiven symbol. It turns out that the latter problem is equivalent to theoriginal one.

All instantiations of the greedy algorithm for the shortest superstring problem are equivalent