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 Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We present a new approach to approximating the Maximum Duo-Preservation String Mapping Problem (MPSM) based on massaging the constraints into a tractable matching problem. MPSM was introduced in Chen, Chen, Samatova, Peng, Wang, and Tang [10] as the complement to the well-studied Minimum Common String Partition problem (MCSP). Prior work also considers the k-MPSM and k-MCSP variants in which each letter occurs at most k times in each string. The authors of [10] showed a k2-appoximation for k ≥ 3 and 2-approximation for k = 2. Boria, Kurpisz, Leppänen, and Mastrolilli [6] gave a 4-approximation independent of k and showed that even 2-MPSM is APX-Hard. A series of improvements led to the current best bounds of a (2+ )approximation for any > 0 in nO(1/ ) time for strings of length n and a 2.67-approximation running in O(n2) time, both by Dudek, Gawrychowski, and Ostropolski-Nalewaja [16]. Here, we show that a 2.67-approximation can surprisingly be achieved in O(n) time for alphabets of constant size and O(n+ α7) for alphabets of size α. Recently, Mehrabi [28] introduced the more general weighted variant, Maximum Weight DuoPreservation String Mapping (MWPSM) and provided a 6-approximation. Our approach gives a 2.67-approximation to this problem running in O(n3) time. This approach can also find an 8/(3(1− ))-approximation to MWPSM for any > 0 in O(n2 −1 lg −1) time using the approximate weighted matching algorithm of Duan and Pettie [15]. Finally, we introduce the first streaming algorithm for MPSM. We show that a single pass suffices to find a 4-approximation on the size of an optimal solution using only O(α2 lgn) space. 2012 ACM Subject Classification Theory of computation → Pattern matching

Fast Matching-based Approximations for Maximum Duo-Preservation String Mapping and its Weighted Variant