Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Erratum: The Approximability of the Exemplar Breakpoint Distance Problem
verfasst von : Zhixiang Chen, Bin Fu, Binhai Zhu
Erschienen in: Frontiers in Algorithmics and Algorithmic Aspects in Information and Management
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The paper “The Approximability of the Exemplar Breakpoint Distance Problem” [1],, which appeared in AAIM 2006, contained several negative results and one positive result — a claimed
O
(log
n
)-factor greedy approximation for the One-sided Exemplar Breakpoint Distance Problem. Here, we show that the analysis was incorrect and the approximation factor of the greedy algorithm could be Θ(
n
), where
n
is the size of the alphabet.