Brubach, Brian
Fast Matchingbased Approximations for Maximum DuoPreservation String Mapping and its Weighted Variant
Abstract
We present a new approach to approximating the Maximum DuoPreservation 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 [Chen et al., 2014] as the complement to the wellstudied Minimum Common String Partition problem (MCSP). Prior work also considers the kMPSM and kMCSP variants in which each letter occurs at most k times in each string. The authors of [Chen et al., 2014] showed a k^2appoximation for k >= 3 and 2approximation for k = 2. Boria, Kurpisz, Leppänen, and Mastrolilli [Boria et al., 2014] gave a 4approximation independent of k and showed that even 2MPSM is APXHard. A series of improvements led to the current best bounds of a (2 + epsilon)approximation for any epsilon > 0 in n^{O(1/epsilon)} time for strings of length n and a 2.67approximation running in O(n^2) time, both by Dudek, Gawrychowski, and OstropolskiNalewaja [Dudek et al., 2017]. Here, we show that a 2.67approximation can surprisingly be achieved in O(n) time for alphabets of constant size and O(n + alpha^7) for alphabets of size alpha.
Recently, Mehrabi [Mehrabi, 2017] introduced the more general weighted variant, Maximum Weight DuoPreservation String Mapping (MWPSM) and provided a 6approximation. Our approach gives a 2.67approximation to this problem running in O(n^3) time. This approach can also find an 8/(3(1epsilon))approximation to MWPSM for any epsilon > 0 in O(n^2 epsilon^{1} lg{epsilon^{1}}) time using the approximate weighted matching algorithm of Duan and Pettie [Duan and Pettie, 2014].
Finally, we introduce the first streaming algorithm for MPSM. We show that a single pass suffices to find a 4approximation on the size of an optimal solution using only O(alpha^2 lg{n}) space.
BibTeX  Entry
@InProceedings{brubach:LIPIcs:2018:8706,
author = {Brian Brubach},
title = {{Fast Matchingbased Approximations for Maximum DuoPreservation String Mapping and its Weighted Variant}},
booktitle = {Annual Symposium on Combinatorial Pattern Matching (CPM 2018)},
pages = {5:15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770743},
ISSN = {18688969},
year = {2018},
volume = {105},
editor = {Gonzalo Navarro and David Sankoff and Binhai Zhu},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2018/8706},
URN = {urn:nbn:de:0030drops87066},
doi = {10.4230/LIPIcs.CPM.2018.5},
annote = {Keywords: approximation algorithm, maximum duopreservation string mapping, minimum common string partition, string comparison, streaming algorithm, comparative}
}
18.05.2018
Keywords: 

approximation algorithm, maximum duopreservation string mapping, minimum common string partition, string comparison, streaming algorithm, comparative 
Seminar: 

Annual Symposium on Combinatorial Pattern Matching (CPM 2018)

Issue date: 

2018 
Date of publication: 

18.05.2018 