{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,19]],"date-time":"2024-03-19T12:27:40Z","timestamp":1710851260742},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T00:00:00Z","timestamp":1368748800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s10878-013-9622-z","type":"journal-article","created":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T10:26:05Z","timestamp":1368699965000},"page":"859-883","source":"Crossref","is-referenced-by-count":4,"title":["A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem"],"prefix":"10.1007","volume":"29","author":[{"given":"Theodoros","family":"Gevezes","sequence":"first","affiliation":[]},{"given":"Leonidas","family":"Pitsoulis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,17]]},"reference":[{"key":"9622_CR1","first-page":"494","volume-title":"Algorithms and data structures, volume 955. Lecture notes in computer science","author":"C Armen","year":"1995","unstructured":"Armen C, Stein C (1995a) Improved length bounds for the shortest superstring problem. In: Akl S, Dehne F, Jorg-Rudiger S, Santoro N (eds) Algorithms and data structures, volume 955. Lecture notes in computer science. Springer, Berlin, pp 494\u2013505"},{"issue":"2","key":"9622_CR2","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1089\/cmb.1995.2.307","volume":"2","author":"C Armen","year":"1995","unstructured":"Armen C, Stein C (1995b) Short superstrings and the structure of overlapping strings. J Comput Biol 2(2):307\u2013332","journal-title":"J Comput Biol"},{"key":"9622_CR3","first-page":"87","volume-title":"Combinatorial pattern matching, volume 1075. Lecture notes in computer science","author":"C Armen","year":"1996","unstructured":"Armen C, Stein C (1996) A $$2 \\frac{2}{3}$$ 2 2 3 -approximation algorithm for the shortest superstring problem. In: Hirschberg D, Myers G (eds) Combinatorial pattern matching, volume 1075. Lecture notes in computer science. Springer, Berlin, pp 87\u2013101"},{"key":"9622_CR4","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45:501\u2013555","journal-title":"J ACM"},{"issue":"3","key":"9622_CR5","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1016\/S0022-5193(88)80246-7","volume":"135","author":"W Bains","year":"1988","unstructured":"Bains W, Smith GC (1988) A novel method for nucleic acid sequence determination. J Theor Biol 135(3):303\u2013307","journal-title":"J Theor Biol"},{"key":"9622_CR6","doi-asserted-by":"crossref","unstructured":"Blum A, Jiang T, Li M, Tromp J, Yannakakis M (1991) Linear approximation of shortest superstrings. In: Proceedings of the twenty-third annual ACM symposium on theory of computing, STOC \u201991, New York, pp. 328\u2013336. ACM. ISBN 0-89791-397-3","DOI":"10.1145\/103418.103455"},{"key":"9622_CR7","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1006\/jagm.1997.0861","volume":"24","author":"D Breslauer","year":"1997","unstructured":"Breslauer D, Jiang T, Jiang Z (1997) Rotations of periodic strings and short superstrings. J Algorithm 24:340\u2013353","journal-title":"J Algorithm"},{"key":"9622_CR8","first-page":"95","volume-title":"Algorithm theory SWAT \u201994, volume 824. Lecture notes in computer science","author":"A Czumaj","year":"1994","unstructured":"Czumaj A, Ga\u0327sieniec L, Piotr\u00f3w M, Rytter W (1994) Parallel and sequential approximation of shortest superstrings. In: Schmidt E, Skyum S (eds) Algorithm theory SWAT \u201994, volume 824. Lecture notes in computer science. Springer, Berlin, pp 95\u2013106"},{"key":"9622_CR9","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/978-1-4615-1507-4_15","volume-title":"Essays and surveys in metaheuristics","author":"P Festa","year":"2002","unstructured":"Festa P, Resende MGC (2002) GRASP: an annotated bibliography. In: Ribeiro CC, Hansen P (eds) Essays and surveys in metaheuristics. Kluwer Academic Publishers, Norwell, pp 325\u2013367"},{"key":"9622_CR10","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/PL00009207","volume":"21","author":"A Frieze","year":"1998","unstructured":"Frieze A, Szpankowski W (1998) Greedy algorithms for the shortest common superstring that are asymptotically optimal. Algorithmica 21:21\u201336","journal-title":"Algorithmica"},{"issue":"1","key":"9622_CR11","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/0022-0000(80)90004-5","volume":"20","author":"J Gallant","year":"1980","unstructured":"Gallant J, Maier D, Storer JA (1980) On finding minimal length superstrings. J Comput Syst Sci 20(1):50\u201358","journal-title":"J Comput Syst Sci"},{"key":"9622_CR12","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1990","unstructured":"Garey MR, Johnson DS (1990) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York"},{"issue":"42743","key":"9622_CR13","first-page":"653","volume":"29","author":"F Glover","year":"2000","unstructured":"Glover F, Laguna M, Rafael M (2000) Fundamentals of scatter search and path relinking. Control Cybern 29(42743):653\u2013684","journal-title":"Control Cybern"},{"key":"9622_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-6089-0","volume-title":"Tabu search","author":"F Glover","year":"1997","unstructured":"Glover F, Laguna M (1997) Tabu search. Kluwer Academic Publishers, Norwell"},{"key":"9622_CR15","unstructured":"Goldberg MK, Lim DT (2001) A learning algorithm for the shortest superstring problem. In: Proceedings of the atlantic symposium on computational biology and genome information and technology, Durham, NC, pp 171\u2013175"},{"key":"9622_CR16","first-page":"153","volume":"73","author":"L Ilie","year":"2006","unstructured":"Ilie L, Popescu C (2006) The shortest common superstring problem and viral genome compression. Fundam Inform 73:153\u2013164","journal-title":"Fundam Inform"},{"key":"9622_CR17","volume-title":"DNA computing, volume 4287. Lecture notes in computer science","author":"L Ilie","year":"2006","unstructured":"Ilie L, Tinta L, Popescu C, Hill KA (2006) Viral genome compression. In: Mao C, Yokomori T (eds) DNA computing, volume 4287. Lecture notes in computer science. Springer, Berlin"},{"key":"9622_CR18","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.ipl.2004.09.012","volume":"93","author":"H Kaplan","year":"2005","unstructured":"Kaplan H, Shafrir N (2005) The greedy algorithm for shortest superstrings. Inform Process Lett 93:13\u201317","journal-title":"Inform Process Lett"},{"key":"9622_CR19","doi-asserted-by":"crossref","unstructured":"Kosaraju SR, Park JK, Stein C (1994) Long tours and short superstrings. In: Proceedings of the 35th annual symposium on foundations of computer science, Washington, pp 166\u2013177. IEEE Computer Society. ISBN 0-8186-6580-7","DOI":"10.1109\/SFCS.1994.365696"},{"key":"9622_CR20","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1287\/ijoc.11.1.44","volume":"11","author":"M Laguna","year":"1999","unstructured":"Laguna M, Mart\u00ed R (1999) Grasp and path relinking for 2-layer straight line crossing minimization. INFORMS J Comput 11:44\u201352","journal-title":"INFORMS J Comput"},{"key":"9622_CR21","doi-asserted-by":"crossref","unstructured":"Li M (1990) Towards a DNA sequencing theory (learning a string). Foundations of Computer Science. In: Proceedings of 31st Annual IEEE Symposium, 22\u201324 Oct 1990","DOI":"10.1109\/FSCS.1990.89531"},{"issue":"15","key":"9622_CR22","doi-asserted-by":"crossref","first-page":"2031","DOI":"10.1093\/bioinformatics\/btr319","volume":"27","author":"Y Lin","year":"2011","unstructured":"Lin Y, Li J, Shen H, Zhang L, Papasian CJ, Deng H-W (2011) Comparative studies of de novo assembly tools for next-generation sequencing technologies. Bioinformatics 27(15):2031\u20132037","journal-title":"Bioinformatics"},{"key":"9622_CR23","first-page":"62","volume-title":"Adaptive and natural computing algorithms, volume 5495. Lecture Notes in computer science","author":"D L\u00f3pez-Rodr\u00edguez","year":"2009","unstructured":"L\u00f3pez-Rodr\u00edguez D, M\u00e9rida-Casermeiro E (2009) Shortest common superstring problem with discrete neural networks. In: Kolehmainen M, Toivanen P, Beliczynski B (eds) Adaptive and natural computing algorithms, volume 5495. Lecture Notes in computer science. Springer, Berlin, pp 62\u201371"},{"key":"9622_CR24","first-page":"244","volume-title":"Combinatorial pattern matching, volume 5029. Lecture notes in computer science","author":"B Ma","year":"2008","unstructured":"Ma B (2008) Why greed works for shortest common superstring problem. In: Ferragina P, Landau G (eds) Combinatorial pattern matching, volume 5029. Lecture notes in computer science. Springer, Berlin, pp 244\u2013254. doi: 10.1007\/978-3-540-69068-9-23"},{"issue":"2","key":"9622_CR25","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1093\/comjnl\/18.2.157","volume":"18","author":"A Mayne","year":"1975","unstructured":"Mayne A, James EB (1975) Information compression by factorising common strings. Comput J 18(2):157\u2013160","journal-title":"Comput J"},{"issue":"1\u20132","key":"9622_CR26","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0304-3975(97)00133-3","volume":"191","author":"M Middendorf","year":"1998","unstructured":"Middendorf M (1998) Shortest common superstrings and scheduling with coordinated starting times. Theor Comput Sci 191(1\u20132):205\u2013214","journal-title":"Theor Comput Sci"},{"key":"9622_CR27","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1145\/321043.321046","volume":"7","author":"CE Miller","year":"1960","unstructured":"Miller CE, Tucker AW, Zemlin RA (1960) Integer programming formulation of traveling salesman problems. J ACM 7:326\u2013329","journal-title":"J ACM"},{"issue":"5","key":"9622_CR28","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ygeno.2008.07.001","volume":"92","author":"O Morozova","year":"2008","unstructured":"Morozova O, Marra MA (2008) Applications of next-generation sequencing technologies in functional genomics. Genomics 92(5):255\u2013264","journal-title":"Genomics"},{"key":"9622_CR29","doi-asserted-by":"crossref","unstructured":"Oliveira C, Pardalos P, Resende M (2004) Grasp with path-relinking for the quadratic assignment problem. In: Ribeiro C, Martins S (eds) Experimental and efficient algorithms, volume 3059. Lecture notes in computer science. Springer, Berlin,pp. 356\u2013368. ISBN 978-3-540-22067-1","DOI":"10.1007\/978-3-540-24838-5_27"},{"key":"9622_CR30","first-page":"55","volume-title":"Graph-theoretic concepts in computer science, volume 1665. Lecture notes in computer science","author":"S Ott","year":"1999","unstructured":"Ott S (1999) Lower bounds for approximating shortest superstrings over an alphabet of size 2. In: Widmayer P, Neyer G, Eidenbenz S (eds) Graph-theoretic concepts in computer science, volume 1665. Lecture notes in computer science. Springer, Berlin, pp 55\u201364"},{"key":"9622_CR31","first-page":"178","volume-title":"Handbook of applied optimization","author":"LS Pitsoulis","year":"2002","unstructured":"Pitsoulis LS, Resende MGC (2002) Greedy randomized adaptive search procedures. In: Pardalos PM, Resende MGC (eds) Handbook of applied optimization. Oxford University Press, Oxford, pp 178\u2013183"},{"key":"9622_CR32","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1007\/0-387-25383-1_2","volume-title":"Metaheuristics: progress as real problem solvers","author":"MGC Resende","year":"2005","unstructured":"Resende MGC, Ribeiro CC (2005) Grasp with path-relinking: recent advances and applications. In: Ibaraki T, Nonobe K, Yagiura M (eds) Metaheuristics: progress as real problem solvers. Springer, Berlin, pp 29\u201363"},{"key":"9622_CR33","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1023\/B:HEUR.0000019986.96257.50","volume":"10","author":"MGC Resende","year":"2004","unstructured":"Resende MGC, Werneck RF (2004) A hybrid heuristic for the $$p$$ p -median problem. J Heuristics 10:59\u201388","journal-title":"J Heuristics"},{"key":"9622_CR34","unstructured":"Storer JA, Szymanski TG (1978) The macro model for data compression (extended abstract). In: Proceedings of the tenth annual ACM symposium on theory of computing, STOC \u201978, New York, pp. 30\u201339"},{"key":"9622_CR35","doi-asserted-by":"crossref","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer JA, Szymanski TG (1982) Data compression via textual substitution. J ACM 29:928\u2013951","journal-title":"J ACM"},{"key":"9622_CR36","doi-asserted-by":"crossref","first-page":"954","DOI":"10.1137\/S0097539796324661","volume":"29","author":"Z Sweedyk","year":"1999","unstructured":"Sweedyk Z (1999) A $$2\\frac{1}{2}$$ 2 1 2 -approximation algorithm for shortest superstring. SIAM J Comput 29:954\u2013986","journal-title":"SIAM J Comput"},{"issue":"1","key":"9622_CR37","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0304-3975(88)90167-3","volume":"57","author":"J Tarhio","year":"1988","unstructured":"Tarhio J, Ukkonen E (1988) A greedy approximation algorithm for constructing shortest common superstrings. Theor Comput Sci 57(1):131\u2013145","journal-title":"Theor Comput Sci"},{"key":"9622_CR38","doi-asserted-by":"crossref","unstructured":"Teng S-H, Yao F (1993) Approximating shortest superstrings. In: Proceedings of the 1993 IEEE 34th annual foundations of computer science, pp. 158\u2013165","DOI":"10.1109\/SFCS.1993.366871"},{"issue":"6","key":"9622_CR39","doi-asserted-by":"crossref","first-page":"1867","DOI":"10.1109\/18.782108","volume":"45","author":"E Yang","year":"1999","unstructured":"Yang E, Zhang Z (1999) The shortest common superstring problem: average case analysis for both exact and approximate matching. IEEE Trans Inf Theory 45(6):1867\u20131886","journal-title":"IEEE Trans Inf Theory"},{"issue":"5","key":"9622_CR40","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1109\/TEVC.2004.831260","volume":"8","author":"A Zaritsky","year":"2004","unstructured":"Zaritsky A, Sipper M (2004) The preservation of favored building blocks in the struggle for fitness: the puzzle algorithm. IEEE Trans Evol Comput 8(5):443\u2013455","journal-title":"IEEE Trans Evol Comput"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9622-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9622-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9622-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T21:52:21Z","timestamp":1563054741000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9622-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,17]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9622"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9622-z","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,17]]}}}