%0 Book Section %1 springerlink:10.1007/978-3-642-32512-0_3 %A Awasthi, Pranjal %A Blum, Avrim %A Morgenstern, Jamie %A Sheffet, Or %B Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques %C Berlin / Heidelberg %D 2012 %E Gupta, Anupam %E Jansen, Klaus %E Rolim, José %E Servedio, Rocco %I Springer %K approximation phylogeny %P 25-36 %R 10.1007/978-3-642-32512-0_3 %T Additive Approximation for Near-Perfect Phylogeny Construction %V 7408 %X We study the problem of constructing phylogenetic trees for a given set of species. The problem is formulated as that of finding a minimum Steiner tree on n points over the Boolean hypercube of dimension d . It is known that an optimal tree can be found in linear time 1 if the given dataset has a perfect phylogeny, i.e. cost of the optimal phylogeny is exactly d . Moreover, if the data has a near-perfect phylogeny, i.e. the cost of the optimal Steiner tree is d + q , it is known 2 that an exact solution can be found in running time which is polynomial in the number of species and d , yet exponential in q . In this work, we give a polynomial-time algorithm (in both d and q ) that finds a phylogenetic tree of cost d + O ( q 2 ). This provides the best guarantees known—namely, a (1 + o (1))-approximation—for the case , broadening the range of settings for which near-optimal solutions can be efficiently found. We also discuss the motivation and reasoning for studying such additive approximations. %@ 978-3-642-32511-3

@incollection{springerlink:10.1007/978-3-642-32512-0_3, abstract = {We study the problem of constructing phylogenetic trees for a given set of species. The problem is formulated as that of finding a minimum Steiner tree on n points over the Boolean hypercube of dimension d . It is known that an optimal tree can be found in linear time [1] if the given dataset has a perfect phylogeny, i.e. cost of the optimal phylogeny is exactly d . Moreover, if the data has a near-perfect phylogeny, i.e. the cost of the optimal Steiner tree is d + q , it is known [2] that an exact solution can be found in running time which is polynomial in the number of species and d , yet exponential in q . In this work, we give a polynomial-time algorithm (in both d and q ) that finds a phylogenetic tree of cost d + O ( q 2 ). This provides the best guarantees known—namely, a (1 + o (1))-approximation—for the case , broadening the range of settings for which near-optimal solutions can be efficiently found. We also discuss the motivation and reasoning for studying such additive approximations.}, added-at = {2012-08-31T21:50:30.000+0200}, address = {Berlin / Heidelberg}, affiliation = {Carnegie Mellon University, Pittsburgh, 5000 Forbes Ave., Pittsburgh, PA 15213, USA}, author = {Awasthi, Pranjal and Blum, Avrim and Morgenstern, Jamie and Sheffet, Or}, biburl = {https://www.bibsonomy.org/bibtex/2cf240e8da84b85bfedfa16d3bf6662f4/ytyoun}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques}, doi = {10.1007/978-3-642-32512-0_3}, editor = {Gupta, Anupam and Jansen, Klaus and Rolim, José and Servedio, Rocco}, interhash = {247a86ec9df020fe9966ad03dff688ba}, intrahash = {cf240e8da84b85bfedfa16d3bf6662f4}, isbn = {978-3-642-32511-3}, keyword = {Computer Science}, keywords = {approximation phylogeny}, pages = {25-36}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, timestamp = {2016-06-14T14:43:13.000+0200}, title = {Additive Approximation for Near-Perfect Phylogeny Construction}, volume = 7408, year = 2012 }