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 CPM 2017, Amir et al. introduce a problem, named \emph{approximate stringcover} (\textbf{ACP}), motivated by many aplications including coding andautomata theory, formal language theory, combinatorics and molecular biology. A\emph{cover} of a string $T$ is a string $C$ for which every letter of $T$ lieswithin some occurrence of $C$. The input of the \textbf{ACP} problem consistsof a string $T$ and an integer $m$ (less than the length of $T$), and the goalis to find a string $C$ of length $m$ that covers a string $T'$ which is asclose to $T$ as possible (under some predefined distance). Amir et al. studythe problem for the Hamming distance.  In this paper we continue the work of Amir et al. and show the followingresults:  We show an approximation algorithm for the \textbf{ACP} with an approximationratio of $\sqrt{OPT}$, where OPT is the size of the optimal solution.  We provide an FPT algorithm with respect to the alphabet size. \item The\textbf{ACP} problem naturally extends to pseudometrics. Moreover, we show thatfor some family of pseudometrics, that we term \emph{homogenous additivepseudometrics}, the complexity of \textbf{ACP} remains unchanged.  We partially give an answer to an open problem of Amir et al. and show thatthe Hamming distance over an unbounded alphabet is equivalent to an extendedmetric over a fixed sized alphabet.

Hardness and algorithmic results for the approximate cover problem