{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,28]],"date-time":"2026-07-28T12:15:26Z","timestamp":1785240926197,"version":"3.55.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642325113","type":"print"},{"value":"9783642325120","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32512-0_3","type":"book-chapter","created":{"date-parts":[[2012,7,20]],"date-time":"2012-07-20T22:21:08Z","timestamp":1342822868000},"page":"25-36","source":"Crossref","is-referenced-by-count":4,"title":["Additive Approximation for Near-Perfect Phylogeny Construction"],"prefix":"10.1007","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jamie","family":"Morgenstern","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Or","family":"Sheffet","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/11415770_44","volume-title":"Research in Computational Molecular Biology","author":"Z. Ding","year":"2005","unstructured":"Ding, Z., Filkov, V., Gusfield, D.: A Linear-Time Algorithm for the Perfect Phylogeny Haplotyping (PPH) Problem. In: Miyano, S., Mesirov, J., Kasif, S., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2005. LNCS (LNBI), vol.\u00a03500, pp. 585\u2013600. Springer, Heidelberg (2005)"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"667","DOI":"10.1007\/11786986_58","volume-title":"Automata, Languages and Programming","author":"G.E. Blelloch","year":"2006","unstructured":"Blelloch, G.E., Dhamdhere, K., Halperin, E., Ravi, R., Schwartz, R., Sridhar, S.: Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 667\u2013678. Springer, Heidelberg (2006)"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge University Press (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"3_CR4","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford lecture series in mathematics and its applications. Oxford University Press (2003)"},{"issue":"5712","key":"3_CR5","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1126\/science.1105436","volume":"307","author":"D.A. Hinds","year":"2005","unstructured":"Hinds, D.A., Stuve, L.L., Nilsen, G.B., Halperin, E., Eskin, E., Ballinger, D.G., Frazer, K.A., Cox, D.R.: Whole-genome patterns of common dna variation in three human populations. Science\u00a0307(5712), 1072\u20131079 (2005)","journal-title":"Science"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"The international hapmap project. Nature\u00a0426(6968), 789\u2013796 (2003)","DOI":"10.1038\/nature02168"},{"key":"3_CR7","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1109\/TCBB.2008.13","volume":"7","author":"N. Alon","year":"2010","unstructured":"Alon, N., Chor, B., Pardi, F., Rapoport, A.: Approximate maximum parsimony and ancestral maximum likelihood. IEEE\/ACM Trans. Comput. Biol. Bioinformatics\u00a07, 183\u2013187 (2010)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"3_CR8","unstructured":"Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs. In: SODA, pp. 770\u2013779. Society for Industrial and Applied Mathematics (2000)"},{"key":"3_CR9","unstructured":"Robins, G., Zelikovsky, A.: Improved steiner tree approximation in graphs (2000)"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/S0895480101393155","volume":"19","author":"G. Robins","year":"2005","unstructured":"Robins, G., Zelikovsky, A.: Tighter bounds for graph steiner tree approximation. SIAM Journal on Discrete Mathematics\u00a019, 122\u2013134 (2005)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"3_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-642-12683-3_24","volume-title":"Research in Computational Molecular Biology","author":"N. Misra","year":"2010","unstructured":"Misra, N., Blelloch, G., Ravi, R., Schwartz, R.: Generalized Buneman Pruning for Inferring the Most Parsimonious Multi-state Phylogeny. In: Berger, B. (ed.) RECOMB 2010. LNCS, vol.\u00a06044, pp. 369\u2013383. Springer, Heidelberg (2010)"},{"key":"3_CR12","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1137\/S0097539799350839","volume":"32","author":"D. Fern\u00e1ndez-Baca","year":"2003","unstructured":"Fern\u00e1ndez-Baca, D., Lagergren, J.: A polynomial-time algorithm for near-perfect phylogeny. SIAM J. Comput.\u00a032, 1115\u20131127 (2003)","journal-title":"SIAM J. Comput."},{"key":"3_CR13","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85\u2013103. Plenum, New York (1972)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Foulds, L.R., Graham, R.L.: The Steiner problem in phylogeny is NP-complete. Adv. Appl. Math.\u00a03 (1982)","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"3_CR15","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1109\/TCBB.2007.1070","volume":"4","author":"S. Sridhar","year":"2007","unstructured":"Sridhar, S., Dhamdhere, K., Blelloch, G., Halperin, E., Ravi, R., Schwartz, R.: Algorithms for efficient near-perfect phylogenetic tree reconstruction in theory and practice. IEEE\/ACM Trans. Comput. Biol. Bioinformatics\u00a04, 561\u2013571 (2007)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/j.tcs.2005.10.004","volume":"351","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci.\u00a0351, 337\u2013350 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Agarwala, R., Fernandez-Baca, D.: A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed. In: SFCS, pp. 140\u2013147 (November 1993)","DOI":"10.1109\/SFCS.1993.366873"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Byrka, J., Grandoni, F., Rothvo\u00df, T., Sanit\u00e0, L.: An improved lp-based approximation for steiner tree. In: STOC. ACM (2010)","DOI":"10.1145\/1806689.1806769"},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/3-540-55719-9_80","volume-title":"Automata, Languages and Programming","author":"H.L. Bodlaender","year":"1992","unstructured":"Bodlaender, H.L., Fellows, M.R., Warnow, T.: Two Strikes against Perfect Phylogeny. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 273\u2013283. Springer, Heidelberg (1992)"},{"key":"3_CR20","first-page":"573","volume":"24","author":"H. Takahashi","year":"1980","unstructured":"Takahashi, H., Matsuyama, A.: An approximate solution for the steiner problem in graphs. Mathematica Japonica\u00a024, 573\u2013577 (1980)","journal-title":"Mathematica Japonica"},{"key":"3_CR21","unstructured":"Berman, P., Ramaiyer, V.: Improved approximations for the steiner tree problem. In: SODA, pp. 325\u2013334 (1992)"},{"key":"3_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1007\/BFb0023489","volume-title":"STACS 97","author":"H.J. Pr\u00f6mel","year":"1997","unstructured":"Pr\u00f6mel, H.J., Steger, A.: RNC-Approximation Algorithms for the Steiner Problem. In: Reischuk, R., Morvan, M. (eds.) STACS 1997. LNCS, vol.\u00a01200, pp. 559\u2013570. Springer, Heidelberg (1997)"},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1023\/A:1009758919736","volume":"1","author":"M. Karpinski","year":"1995","unstructured":"Karpinski, M., Zelikovsky, A.: New approximation algorithms for the steiner tree problems. Journal of Combinatorial Optimization\u00a01, 47\u201365 (1995)","journal-title":"Journal of Combinatorial Optimization"},{"key":"3_CR24","unstructured":"Zelikovsky, A.: Better approximation bounds for the network and euclidean steiner tree problems. Technical report (1996)"},{"key":"3_CR25","unstructured":"Hougardy, S., Promel, H.J.: A 1.598 approximation algorithm for the steiner problem in graphs. In: SODA, pp. 448\u2013453 (1999)"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Borchers, A., Du, D.Z.: The k-steiner ratio in graphs. In: STOC, pp. 641\u2013649. ACM (1995)","DOI":"10.1145\/225058.225282"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32512-0_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,5]],"date-time":"2025-04-05T03:25:47Z","timestamp":1743823547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32512-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642325113","9783642325120"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32512-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}