{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:13:27Z","timestamp":1759637607310,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520001","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"317-330","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Improved approximation guarantees for shortest superstrings using cycle classification by overlap to length ratios"],"prefix":"10.1145","author":[{"given":"Matthias","family":"Englert","sequence":"first","affiliation":[{"name":"University of Warwick, UK"}]},{"given":"Nicolaos","family":"Matsakis","sequence":"additional","affiliation":[{"name":"n.n., n.n."}]},{"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Charles University in Prague, Czechia"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60220-8_88"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00065-1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0861"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0823"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009207"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90004-5"},{"key":"e_1_3_2_1_8_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S . Johnson . 1979 . Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman . Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-0808-0_10"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"e_1_3_2_1_11_1","first-page":"1","article-title":"The Shortest Common Superstring Problem and Viral Genome Compression","volume":"73","author":"Ilie Lucian","year":"2006","unstructured":"Lucian Ilie and Cristian Popescu . 2006 . The Shortest Common Superstring Problem and Viral Genome Compression . Fundamenta Informaticae , 73 , 1 - 2 (2006), 153\u2013164. Lucian Ilie and Cristian Popescu. 2006. The Shortest Common Superstring Problem and Viral Genome Compression. Fundamenta Informaticae, 73, 1-2 (2006), 153\u2013164.","journal-title":"Fundamenta Informaticae"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082041"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.012"},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 19th Computing: The Australasian Theory Symposium (CATS). 27\u201336","author":"Karpinski Marek","year":"2013","unstructured":"Marek Karpinski and Richard Schmied . 2013 . Improved Inapproximability Results for the Shortest Superstring and Related Problems . In Proceedings of the 19th Computing: The Australasian Theory Symposium (CATS). 27\u201336 . Marek Karpinski and Richard Schmied. 2013. Improved Inapproximability Results for the Shortest Superstring and Related Problems. In Proceedings of the 19th Computing: The Australasian Theory Symposium (CATS). 27\u201336."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365696"},{"volume-title":"Computational Molecular Biology: Sources and Methods for Sequence Analysis","author":"Lesk Arthur M.","key":"e_1_3_2_1_16_1","unstructured":"Arthur M. Lesk . 1988. Computational Molecular Biology: Sources and Methods for Sequence Analysis . Oxford University Press . Arthur M. Lesk. 1988. Computational Molecular Biology: Sources and Methods for Sequence Analysis. Oxford University Press."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89531"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.014"},{"key":"e_1_3_2_1_19_1","unstructured":"Marcin Mucha. 2007. A Tutorial on Shortest Superstring Approximation. https:\/\/www.mimuw.edu.pl\/ mucha\/teaching\/aa2008\/ss.pdf [Accessed 28-October-2021]  Marcin Mucha. 2007. A Tutorial on Shortest Superstring Approximation. https:\/\/www.mimuw.edu.pl\/ mucha\/teaching\/aa2008\/ss.pdf [Accessed 28-October-2021]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.69"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1515\/itit-2015-0047"},{"key":"e_1_3_2_1_22_1","unstructured":"Katarzyna Paluch. 2020. New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. arxiv:2005.10800  Katarzyna Paluch. 2020. New Approximation Algorithms for Maximum Asymmetric Traveling Salesman and Shortest Superstring. arxiv:2005.10800"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2012.501"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796324661"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90167-3"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794286125"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90044-8"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520001","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520001","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:39Z","timestamp":1750268979000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":27,"alternative-id":["10.1145\/3519935.3520001","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520001","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}