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 Superstring problem, we are given a set of strings and we areasking for a common superstring, which has the minimum number of characters.The Shortest Superstring problem is NP-hard and several constant-factorapproximation algorithms are known for it. Of particular interest is the GREEDYalgorithm, which repeatedly merges two strings of maximum overlap until asingle string remains. The GREEDY algorithm, being simpler than otherwell-performing approximation algorithms for this problem, has attractedattention since the 1980s and is commonly used in practical applications.  Tarhio and Ukkonen (TCS 1988) conjectured that GREEDY gives a2-approximation. In a seminal work, Blum, Jiang, Li, Tromp, and Yannakakis(STOC 1991) proved that the superstring computed by GREEDY is a4-approximation, and this upper bound was improved to 3.5 by Kaplan and Shafrir(IPL 2005).  We show that the approximation guarantee of GREEDY is at most$(13+\sqrt{57})/6 \approx 3.425$, making the first progress on this questionsince 2005. Furthermore, we prove that the Shortest Superstring can beapproximated within a factor of $(37+\sqrt{57})/18\approx 2.475$, improvingslightly upon the currently best $2\frac{11}{23}$-approximation algorithm byMucha (SODA 2013).

Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios