{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:13Z","timestamp":1740122473697,"version":"3.37.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T00:00:00Z","timestamp":1595635200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11971139","11771114"],"award-info":[{"award-number":["11971139","11771114"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11571252","61370052"],"award-info":[{"award-number":["11571252","61370052"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972228","61672323"],"award-info":[{"award-number":["61972228","61672323"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["71701162"],"award-info":[{"award-number":["71701162"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Humanities and Social Science Foundation of Ministry of Education of China","award":["18YJC630114"],"award-info":[{"award-number":["18YJC630114"]}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["201508330054"],"award-info":[{"award-number":["201508330054"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Humanities and Social Science Foundation of Ministry of Education of China","award":["18YJAZH080"],"award-info":[{"award-number":["18YJAZH080"]}]},{"name":"Youth Innovation Team of Shaanxi Universities"},{"DOI":"10.13039\/501100011710","name":"Shaanxi Provincial Science and Technology Department","doi-asserted-by":"publisher","award":["2020JQ-654"],"award-info":[{"award-number":["2020JQ-654"]}],"id":[{"id":"10.13039\/501100011710","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,10]]},"DOI":"10.1007\/s10878-020-00621-0","type":"journal-article","created":{"date-parts":[[2020,7,25]],"date-time":"2020-07-25T13:03:47Z","timestamp":1595682227000},"page":"806-824","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A $$(1.4 + \\epsilon )$$-approximation algorithm for the 2-Max-Duo problem"],"prefix":"10.1007","volume":"40","author":[{"given":"Yong","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4283-3396","authenticated-orcid":false,"given":"Guohui","family":"Lin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tian","family":"Liu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Taibo","family":"Luo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing","family":"Su","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yao","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,7,25]]},"reference":[{"key":"621_CR1","doi-asserted-by":"crossref","unstructured":"Beretta S, Castelli M, Dondi R (2016a) Corrigendum to \u201cParameterized tractability of the maximum-duo preservation string mapping problem\u201d [646(2016), 16\u201325]. Theoret Comput Sci 653:108\u2013110","DOI":"10.1016\/j.tcs.2016.09.015"},{"key":"621_CR2","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1016\/j.tcs.2016.07.011","volume":"646","author":"S Beretta","year":"2016","unstructured":"Beretta S, Castelli M, Dondi R (2016b) Parameterized tractability of the maximum-duo preservation string mapping problem. Theoret Comput Sci 646:16\u201325","journal-title":"Theoret Comput Sci"},{"key":"621_CR3","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P Berman","year":"1999","unstructured":"Berman P, Fujito T (1999) On approximation properties of the independent set problem for low degree graphs. Theory Comput Syst 32:115\u2013132","journal-title":"Theory Comput Syst"},{"key":"621_CR4","doi-asserted-by":"crossref","unstructured":"Berman P, Karpinski M (1999) On some tighter inapproximability results. In: Proceedings of the of 26th international colloquium on automata, languages and programming (ICALP\u201999), pp 200\u2013209","DOI":"10.1007\/3-540-48523-6_17"},{"key":"621_CR5","doi-asserted-by":"crossref","unstructured":"Boria N, Kurpisz A, Lepp\u00e4nen S, Mastrolilli M (2014) Improved approximation for the maximum duo-preservation string mapping problem. In: Proceedings of the 14th international workshop on algorithms in bioinformatics (WABI 2014), volume 8701 of LNBI, pp 14\u201325","DOI":"10.1007\/978-3-662-44753-6_2"},{"key":"621_CR6","unstructured":"Boria N, Cabodi G, Camurati P, Palena M, Pasini P, Quer S (2016) A 7\/2-approximation algorithm for the maximum duo-preservation string mapping problem. In: Proceedings of the 27th annual symposium on combinatorial pattern matching (CPM 2016), volume 54 of LIPIcs, pp 11:1\u201311:8"},{"key":"621_CR7","doi-asserted-by":"crossref","unstructured":"Brubach B (2016) Further improvement in approximating the maximum duo-preservation string mapping problem. In: Proceedings of the 16th international workshop on algorithms in bioinformatics (WABI 2016), volume 9838 of LNBI, pp 52\u201364","DOI":"10.1007\/978-3-319-43681-4_5"},{"key":"621_CR8","doi-asserted-by":"crossref","unstructured":"Bulteau L, Fertin G, Komusiewicz C, Rusu I (2013) A fixed-parameter algorithm for minimum common string partition with few duplications. In: Proceedings of the 13th international workshop on algorithms in bioinformatics (WABI 2013), volume 8126 of LNBI, pp 244\u2013258","DOI":"10.1007\/978-3-642-40453-5_19"},{"key":"621_CR9","doi-asserted-by":"crossref","unstructured":"Bulteau L, Komusiewicz C (2014) Minimum common string partition parameterized by partition size is fixed-parameter tractable. In: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms (SODA\u201914), pp 102\u2013121","DOI":"10.1137\/1.9781611973402.8"},{"key":"621_CR10","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1109\/TCBB.2005.48","volume":"2","author":"X Chen","year":"2005","unstructured":"Chen X, Zheng J, Fu Z, Nan P, Zhong Y, Lonardi S, Jiang T (2005) Assignment of orthologous genes via genome rearrangement. IEEE\/ACM Trans Comput Biol Bioinf 2:302\u2013315","journal-title":"IEEE\/ACM Trans Comput Biol Bioinf"},{"key":"621_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2014.02.017","volume":"530","author":"W Chen","year":"2014","unstructured":"Chen W, Chen Z, Samatova NF, Peng L, Wang J, Tang M (2014) Solving the maximum duo-preservation string mapping problem with linear programming. Theoret Comput Sci 530:1\u201311","journal-title":"Theoret Comput Sci"},{"key":"621_CR12","doi-asserted-by":"crossref","unstructured":"Chrobak M, Kolman P, Sgall J (2004) The greedy algorithm for the minimum common string partition problem. In: Proceedings of the 7th international workshop on approximation algorithms for combinatorial optimization problems (APPROX 2004) and the 8th international workshop on randomization and computation (RANDOM 2004), volume 3122 of LNCS, pp 84\u201395","DOI":"10.1007\/978-3-540-27821-4_8"},{"key":"621_CR13","doi-asserted-by":"publisher","first-page":"2:1","DOI":"10.1145\/1186810.1186812","volume":"3","author":"G Cormode","year":"2007","unstructured":"Cormode G, Muthukrishnan S (2007) The string edit distance matching problem with moves. ACM Trans Algorithms 3:2:1\u20132:19","journal-title":"ACM Trans Algorithms"},{"key":"621_CR14","doi-asserted-by":"crossref","unstructured":"Damaschke P (2008) Minimum common string partition parameterized. In: Proceedings of the 8th international workshop on algorithms in bioinformatics (WABI 2008), volume 5251 of LNBI, pp 87\u201398","DOI":"10.1007\/978-3-540-87361-7_8"},{"key":"621_CR15","unstructured":"Dudek B, Gawrychowski P, Ostropolski-Nalewaja P (2017) A family of approximation algorithms for the maximum duo-preservation string mapping problem. In: Proceedings of the 28th annual symposium on combinatorial pattern matching (CPM 2017), volume 78 of LIPIcs, pp 10:1\u201310:14. arXiv:1702.02405"},{"key":"621_CR16","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San Francisco"},{"key":"621_CR17","doi-asserted-by":"crossref","unstructured":"Goldstein A, Kolman P, Zheng J (2004) Minimum common string partition problem: Hardness and approximations. In: Proceedings of the 15th international symposium on algorithms and computation (ISAAC 2004), volume 3341 of LNCS, pp 484\u2013495","DOI":"10.1007\/978-3-540-30551-4_43"},{"key":"621_CR18","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s10878-010-9370-2","volume":"23","author":"H Jiang","year":"2012","unstructured":"Jiang H, Zhu B, Zhu D, Zhu H (2012) Minimum common string partition revisited. J Comb Optim 23:519\u2013527","journal-title":"J Comb Optim"},{"key":"621_CR19","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/j.dam.2006.05.011","volume":"155","author":"P Kolman","year":"2007","unstructured":"Kolman P, Wale\u0144 T (2007) Approximating reversal distance for strings with bounded number of duplicates. Discrete Appl Math 155:327\u2013336","journal-title":"Discrete Appl Math"},{"key":"621_CR20","doi-asserted-by":"crossref","unstructured":"Kolman P, Wale\u0144 T (2006) Reversal distance for strings with duplicates: linear time approximation using hitting set. In: Proceedings of the 4th international workshop on approximation and online algorithms (WAOA 2006), volume 4368 of LNCS, pp 279\u2013289","DOI":"10.1007\/11970125_22"},{"key":"621_CR21","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1227161.1402297","volume":"12","author":"KM Swenson","year":"2008","unstructured":"Swenson KM, Marron M, Earnest-DeYoung JV, Moret BM (2008) Approximating the true evolutionary distance between two genomes. J Exp Algorithmics 12:3\u20135","journal-title":"J Exp Algorithmics"},{"key":"621_CR22","unstructured":"Xu Y, Chen Y, Luo T, Lin G (2017) A local search 2.917-approximation algorithm for duo-preservation string mapping. arXiv:1702.01877"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00621-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00621-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00621-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,24]],"date-time":"2021-07-24T23:34:03Z","timestamp":1627169643000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00621-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,25]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,10]]}},"alternative-id":["621"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00621-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,7,25]]},"assertion":[{"value":"25 July 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}