{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T19:33:57Z","timestamp":1791228837138,"version":"4.1.0"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2006,1]]},"abstract":"<jats:p>We investigate the greedy algorithm for the shortest common superstring problem. We show that the length of the greedy superstring is upper-bounded by the sum of the lengths of an optimal superstring and an optimal cycle cover, provided the greedy algorithm happens to merge the strings in a particular way. Thus, when restricting inputs correspondingly, we verify the well-known greedy conjecture, namely, that the approximation ratio of the greedy algorithm is within a factor of two of the optimum, and actually extend the conjecture considerably. We achieve this bound by systematically combining known conditional inequalities about overlaps and period- and string-lengths with a new familiy of string inequalities. We show that conventional systems of conditional inequalities, including the Monge inequalities, are insufficient to obtain our result.<\/jats:p>","DOI":"10.1137\/040619144","type":"journal-article","created":{"date-parts":[[2008,2,4]],"date-time":"2008-02-04T16:47:50Z","timestamp":1202143670000},"page":"502-522","source":"Crossref","is-referenced-by-count":6,"title":["On the Greedy Superstring Conjecture"],"prefix":"10.1137","volume":"20","author":[{"given":"Maik","family":"Weinard","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"C. Armen and C. Stein,\n                      Improved length bounds for the shortest superstring problem\n                      , in Proceedings of the 4th International Workshop on Algorithms and Data Structures (WADS), S. G. Akl, F. Dehne, J.\u2010R. Sack, and N. Santoro, eds., Lecture Notes in Comput. Sci. 955, Springer\u2010Verlag, New York, 1995, pp. 494\u2013505.","DOI":"10.1007\/3-540-60220-8_88"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00065-1"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/179812.179818"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0861"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"ArturCzumaj, LeszekG\u0105sieniec, MarekPiotr\u00f3w, WojciechRytter, Parallel and sequential approximation of shortest superstrings, Lecture Notes in Comput. Sci., Vol. 824, Springer, Berlin, 1994, 95\u201310695m:68071","DOI":"10.1007\/3-540-58218-5_9"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.09.012"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"R. Kosaraju, J. Park, and C. Stein,\n                      Long tours and short superstrings\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Santa Fe, NM, 1994, IEEE Computer Society Press, Los Alamitos, CA, 1994, pp. 166\u2013177.","DOI":"10.1109\/SFCS.1994.365696"},{"key":"R9","unstructured":"U. Laube and M. Weinard,\n                      Conditional inequalities and the shortest common superstring problem\n                      , in Proceedings of the 4th Prague Stringology Conference, M. \u0160im\u00e1nek and J. Holub, eds., Vydavatelst\u00ed \u010cVUT, Prague, 2004, pp. 124\u2013138."},{"key":"R10","unstructured":"G. Monge,\n                      M\u00e9moire sur la th\u00e9orie des d\u00e9blais et des remblais\n                      , in Histoire de l\u2019Academie Royale des Sciences, Ann\u00e9s MDCCLXXXI, avec les M\u00e9moires de Math\u00e9matique et de Physique, pour la m\u00eame Ann\u00e9e, Tir\u00e9s des Registres de cette Acad\u00e9mie, 1781, pp. 666\u2013704."},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796324661"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(88)90167-3"},{"key":"R13","unstructured":"S. Teng and F. Yao,\n                      Approximating a shortest superstring\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science (FOCS), Palo Alto, CA, 1993, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 158\u2013165."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Weinard and G. Schnitger,\n                      On the greedy superstring conjecture\n                      , in Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FST TCS), Mumbai, India, 2003, P. K. Pandya and J. Radhakrishnan, eds., pp. 387\u2013398.","DOI":"10.1007\/978-3-540-24597-1_33"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/040619144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:07:41Z","timestamp":1787321261000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/040619144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,1]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2006,1]]}},"alternative-id":["10.1137\/040619144"],"URL":"https:\/\/doi.org\/10.1137\/040619144","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,1]]}}}