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/

Zendy Plus

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

Zendy Tools

Zendy Open

We study approximation algorithms for variants of the \emph{median string}problem, which asks for a string that minimizes the sum of edit distances froma given set of $m$ strings of length $n$. Only the straightforward$2$-approximation is known for this NP-hard problem. This problem is motivatede.g.~by computational biology, and belongs to the class of median problems(over different metric spaces), which are fundamental tasks in data analysis.  Our main result is for the Ulam metric, where all strings are permutationsover $[n]$ and each edit operation moves a symbol (deletion plus insertion). Wedevise for this problem an algorithms that breaks the $2$-approximationbarrier, i.e., computes a $(2-\delta)$-approximate median permutation for someconstant $\delta>0$ in time $\tilde{O}(nm^2+n^3)$. We further use thesetechniques to achieve a $(2-\delta)$ approximation for the median stringproblem in the special case where the median is restricted to length $n$ andthe optimal objective is large $\Omega(mn)$.  We also design an approximation algorithm for the following probabilisticmodel of the Ulam median: the input consists of $m$ perturbations of an(unknown) permutation $x$, each generated by moving every symbol to a randomposition with probability (a parameter) $\epsilon>0$. Our algorithm computeswith high probability a $(1+o(1/\epsilon))$-approximate median permutation intime $O(mn^2+n^3)$.

Approximating the Median under the Ulam Metric