环型二元序列的赋权对换排序问题

摘要

研究了环型二元序列的赋权对换排序问题。定义一个长度为l的对换的费用是f(l)=lα,0≤α<1,对环型二元序列的赋权对换排序问题给出了一个O(logn)-近似算法,其中n是环型二元序列的长度。