On the Tightness of the Alternating-Cycle Lower Bound for Sorting by Reversals

Alberto Caprara ()
Additional contact information
Alberto Caprara: DEIS, University of Bologna

Journal of Combinatorial Optimization, 1999, vol. 3, issue 2, No 2, 149-182

Abstract: Abstract We give a theoretical answer to a natural question arising from a few years of computational experiments on the problem of sorting a permutation by the minimum number of reversals, which has relevant applications in computational molecular biology. The experiments carried out on the problem showed that the so-called alternating-cycle lower bound is equal to the optimal solution value in almost all cases, and this is the main reason why the state-of-the-art algorithms for the problem are quite effective in practice. Since worst-case analysis cannot give an adequate justification for this observation, we focus our attention on estimating the probability that, for a random permutation of n elements, the above lower bound is not tight. We show that this probability is low even for small n, and asymptotically Θ(1/n5), i.e., O(1/n5) and Ω(1/n5). This gives a satisfactory explanation to empirical observations and shows that the problem of sorting by reversals and its alternating-cycle relaxation are essentially the same problem, with the exception of a small fraction of “pathological” instances, justifying the use of algorithms which are heavily based on this relaxation. From our analysis we obtain convenient sufficient conditions to test if the alternating-cycle lower bound is tight for a given instance. We also consider the case of signed permutations, for which the analysis is much simpler, and show that the probability that the alternating-cycle lower bound is not tight for a random signed permutation of m elements is asymptotically Θ(1/m2).

Keywords: tightness of lower bounds; sorting by reversals; alternating-cycle relaxation; probability; counting (search for similar items in EconPapers)
Date: 1999
References: View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1023/A:1009838309166 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:3:y:1999:i:2:d:10.1023_a:1009838309166

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/A:1009838309166

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().