摘要
Classicalsortingbyreversalsusestheunit-costmodel,thatis,eachreversalconsumesanequalcost.Thismodellimitsthebiologicalmeaningofsortingbyreversal.Benderandhiscolleaguesextendeditbyassigningacostfunctionf(l)=lαforallα≥0,wherelisthelengthofthereversedsubsequence.Inthispaper,weextendtheirresultsbyconsideringamodelinwhichlongreversalsareprohibited.Usingthesamecostfunctionaboveforpermittedreversals,wepresenttightornearlytightboundsfortheworst-casecostofsortingbyreversals.Thenwedevelopalgorithmstoapproximatetheoptimalcosttosortagiven0/1sequenceaswellasagivenpermutation.OurproposedproblemsaremorebiologicallymeaningfulandmorealgorithmicallygeneralandchallengingthantheproblemconsideredbyBenderetal.Furthermore,ourboundsaretightandnearlytight,whereasouralgorithmsprovidegoodapproximationratioscomparedtotheoptimalcosttosort0/1sequencesorpermutationsbyreversals.
出版日期
2005年02月12日（中国期刊网平台首次上网日期，不代表论文的发表时间）
