%0 Journal Article
%T Design and Performance Evaluation of Sequence Partition Algorithms
%A Bing Yang
%A Jing Chen
%A En-Yue Lu
%A Si-Qing Zheng
%A <br>Bing Yang
%A Jing Chen
%A En-Yue Lu
%A and Si-Qing Zheng
%J 计算机科学技术学报
%D 2008
%I 
%X Tradeoffs between time complexities and solution optimalities are important when selecting algorithms for an NP-hard problem in different applications. Also, the distinction between theoretical upper bound and actual solution optimality for realistic instances of an NP-hard problem is a factor in selecting algorithms in practice. We consider the problem of partitioning a sequence of n distinct numbers into minimum number of monotone (increasing or decreasing) subsequences. This problem is NP-hard and the number of monotone subsequences can reach 2n 41 - 1/2 in the worst case. We introduce a new algorithm, the modified version of the Yehuda-Fogel algorithm, that computes a solution of no more than 2n 41 -1/2 monotone subsequences in O(n1.5) time. Then we perform a comparative experimental study on three algorithms, a known approximation algorithm of approximation ratio 1.71 and time complexity O(n3), a known greedy algorithm of time complexity O(n1.5 log n), and our new modified Yehuda-Fogel algorithm. Our results show that the solutions computed by the greedy algorithm and the modified Yehuda-Fogel algorithm are close to that computed by the approximation algorithm even though the theoretical worst-case error bounds of these two algorithms are not proved to be within a constant time of the optimal solution. Our study indicates that for practical use the greedy algorithm and the modified Yehuda-Fogel algorithm can be good choices if the running time is a major concern.
%K monotone subsequence
%K permutation algorithm
%K NP-complete
%K approximation
%K complexity<br>
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=50F9268018C17D1A4177C7DDA2DA44C3&yid=67289AFF6305E306&vid=EA389574707BDED3&iid=94C357A881DFC066&sid=FD6137FFCE59D193&eid=5A027C8E6C570AAB&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=17