@inbook {14589,
	title = {1.375-Approximation Algorithm for Sorting by Reversals},
	booktitle = {Algorithms {\textemdash} ESA 2002Algorithms {\textemdash} ESA 2002},
	series = {Lecture Notes in Computer Science},
	volume = {2461},
	year = {2002},
	month = {2002///},
	pages = {401 - 408},
	publisher = {Springer Berlin / Heidelberg},
	organization = {Springer Berlin / Heidelberg},
	abstract = {Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals , MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm for a special case of unsigned permutations. The best known approximation algorithm for MIN-SBR, due to Christie, gives a performance ratio of 1.5. In this paper, by exploiting the polynomial time algorithm for sorting signed permutations and by developing a new approximation algorithm for maximum cycle decomposition of breakpoint graphs, we design a new 1.375-algorithm for the MIN-SBR problem.},
	isbn = {978-3-540-44180-9},
	url = {http://dx.doi.org/10.1007/3-540-45749-6_21},
	author = {Berman,Piotr and Hannenhalli, Sridhar and Karpinski,Marek},
	editor = {M{\"o}hring,Rolf and Raman,Rajeev}
}
