{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:47:03Z","timestamp":1725536823707},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642038150"},{"type":"electronic","value":"9783642038167"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_53","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T10:43:03Z","timestamp":1250678583000},"page":"624-635","source":"Crossref","is-referenced-by-count":1,"title":["A Probabilistic PTAS for Shortest Common Superstring"],"prefix":"10.1007","author":[{"given":"Kai","family":"Plociennik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"53_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/3-540-58094-8_15","volume-title":"Combinatorial Pattern Matching","author":"K.S. Alexander","year":"1994","unstructured":"Alexander, K.S.: Shortest Common Superstrings for Strings of Random Letters. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol.\u00a0807, pp. 164\u2013172. Springer, Heidelberg (1994)"},{"key":"53_CR2","unstructured":"Armen, C., Stein, C.: A 2 3\/4 approximation algorithm for the shortest superstring problem. Technical Report PCS-TR94-214, Department of Comp. Sc., Dartmouth College, Hanover, New Hampshire (1994)"},{"key":"53_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/3-540-61258-0_8","volume-title":"Combinatorial Pattern Matching","author":"C. Armen","year":"1996","unstructured":"Armen, C., Stein, C.: A 2 2\/3-Approximation Algorithm for the Shortest Superstring Problem. In: Hirschberg, D.S., Meyers, G. (eds.) CPM 1996. LNCS, vol.\u00a01075, pp. 87\u2013101. Springer, Heidelberg (1996)"},{"issue":"4","key":"53_CR4","doi-asserted-by":"publisher","first-page":"630","DOI":"10.1145\/179812.179818","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A., Jiang, T., Li, M., Tromp, J., Yannakakis, M.: Linear Approximation of Shortest Superstrings. J. ACM\u00a041(4), 630\u2013647 (1994)","journal-title":"J. ACM"},{"key":"53_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-61680-2_56","volume-title":"Algorithms - ESA \u201996","author":"A.M. Frieze","year":"1996","unstructured":"Frieze, A.M., Szpankowski, W.: Greedy Algorithms for the Shortest Common Superstring that are Asymptotically Optimal. In: D\u00edaz, J., Serna, M.J. (eds.) ESA 1996. LNCS, vol.\u00a01136, pp. 194\u2013207. Springer, Heidelberg (1996)"},{"key":"53_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences. Cambridge University Press, Cambridge (1997)"},{"key":"53_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1007\/3-540-58094-8_9","volume-title":"Combinatorial Pattern Matching","author":"T. \u0141uczak","year":"1994","unstructured":"\u0141uczak, T., Szpankowski, W.: A Lossy Data Compression Based on String Matching: Preliminary Analysis and Suboptimal Algorithms. In: Crochemore, M., Gusfield, D. (eds.) CPM 1994. LNCS, vol.\u00a0807, pp. 102\u2013112. Springer, Heidelberg (1994)"},{"key":"53_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-69068-9_23","volume-title":"Combinatorial Pattern Matching","author":"B. Ma","year":"2008","unstructured":"Ma, B.: Why Greed Works for Shortest Common Superstring Problem. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol.\u00a05029, pp. 244\u2013254. Springer, Heidelberg (2008)"},{"issue":"2","key":"53_CR9","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0304-3975(92)00074-2","volume":"125","author":"M. Middendorf","year":"1994","unstructured":"Middendorf, M.: More on the Complexity of Common Superstring and Supersequence Problems. Theor. Comp. Sc.\u00a0125(2), 205\u2013228 (1994)","journal-title":"Theor. Comp. Sc."},{"key":"53_CR10","first-page":"296","volume-title":"Proc. 33rd Ann. ACM Symp. on Th. of Comp.","author":"D.A. Spielman","year":"2001","unstructured":"Spielman, D.A., Teng, S.: Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. In: Proc. 33rd Ann. ACM Symp. on Th. of Comp., pp. 296\u2013305. ACM, New York (2001)"},{"issue":"3","key":"53_CR11","doi-asserted-by":"publisher","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z. Sweedyk","year":"1999","unstructured":"Sweedyk, Z.: A 2 1\/2 Approximation Algorithm for Shortest Superstring. SIAM J. Comput.\u00a029(3), 954\u2013986 (1999)","journal-title":"SIAM J. Comput."},{"key":"53_CR12","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J. Tarhio","year":"1988","unstructured":"Tarhio, J., Ukkonen, E.: A Greedy Approximation Algorithm for Constructing Shortest Common Superstrings. Theor. Comp. Sc.\u00a057, 131\u2013145 (1988)","journal-title":"Theor. Comp. Sc."},{"key":"53_CR13","first-page":"158","volume-title":"34th Ann. Symp. on Found. of Comp. Sc.","author":"S. Teng","year":"1993","unstructured":"Teng, S., Yao, F.: Approximating Shortest Superstring. In: 34th Ann. Symp. on Found. of Comp. Sc., pp. 158\u2013165. IEEE Press, New York (1993)"},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(89)90044-8","volume":"83","author":"J.S. Turner","year":"1989","unstructured":"Turner, J.S.: Approximation Algorithms for the Shortest Common Superstring Problem. Inf. and Comput.\u00a083, 1\u201320 (1989)","journal-title":"Inf. and Comput."},{"key":"53_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1007\/11549345_68","volume-title":"Mathematical Foundations of Computer Science 2005","author":"V. Vassilevska","year":"2005","unstructured":"Vassilevska, V.: Explicit Inapproximability Bounds for the Shortest Superstring Problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol.\u00a03618, pp. 793\u2013800. Springer, Heidelberg (2005)"},{"key":"53_CR16","volume-title":"Approximation Algorithms","author":"V.V. Vazirani","year":"2001","unstructured":"Vazirani, V.V.: Approximation Algorithms. Springer, Heidelberg (2001)"},{"issue":"6","key":"53_CR17","doi-asserted-by":"publisher","first-page":"1867","DOI":"10.1109\/18.782108","volume":"45","author":"E.H. Yang","year":"1999","unstructured":"Yang, E.H., Zhang, Z.: The shortest common superstring problem: Average case analysis for both exact and approximate matching. IEEE Transact. on Inf. Th.\u00a045(6), 1867\u20131886 (1999)","journal-title":"IEEE Transact. on Inf. Th."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,9]],"date-time":"2019-03-09T08:14:58Z","timestamp":1552119298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_53","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}