Design and Performance Evaluation of Sequence Partition Algorithms  

作　　者：杨兵 陈菁 吕恩月 郑斯清 

机构地区：[1]Cisco Systems, 2200 East President George Bush Highway [2]Telecom. Engineering Program, University of Texas at Dallas [3]Department of Mathematics and Computer Science, Salisbury University [4]Department of Computer Science, University of Texas at Dallas

出　　处：《Journal of Computer Science & Technology》2008年第5期711-718,共8页计算机科学技术学报（英文版）

摘　　要：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＋1/1-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＋1/1-1/2]monotone subsequences in O（n^1.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（n^3）, a known greedy algorithm of time complexity O（n^1.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.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＋1/1-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＋1/1-1/2]monotone subsequences in O（n^1.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（n^3）, a known greedy algorithm of time complexity O（n^1.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.

关 键 词：monotone subsequence permutation algorithm NP-COMPLETE APPROXIMATION COMPLEXITY 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]