We use cookies to improve your experience with our site.
Bing Yang, Jing Chen, En-Yue Lu, Si-Qing Zheng. Design and Performance Evaluation of Sequence Partition Algorithms[J]. Journal of Computer Science and Technology, 2008, 23(5): 711-718.
 Citation: Bing Yang, Jing Chen, En-Yue Lu, Si-Qing Zheng. Design and Performance Evaluation of Sequence Partition Algorithms[J]. Journal of Computer Science and Technology, 2008, 23(5): 711-718.

# Design and Performance Evaluation of Sequence Partition Algorithms

• Tradeoffs between timecomplexities and solution optimalities are important when selectingalgorithms for an NP-hard problem in different applications. Also,the distinction between theoretical upper bound and actual solutionoptimality for realistic instances of an NP-hard problem is a factorin selecting algorithms in practice. We consider the problem ofpartitioning a sequence of n distinct numbers into minimum numberof monotone (increasing or decreasing) subsequences. This problem isNP-hard and the number of monotone subsequences can reach\big\lfloor \sqrt2n+\frac 14-\frac 12 \big\rfloor in the worstcase. We introduce a new algorithm, the modified version of theYehuda-Fogel algorithm, that computes a solution of no more than\big\lfloor \sqrt2n+\frac 14-\frac 12 \big\rfloor monotonesubsequences in O(n^1.5) time. Then we perform a comparativeexperimental study on threealgorithms, a known approximation algorithm of approximation ratio1.71 and time complexity O(n^3), a known greedy algorithm oftime complexity O(n^1.5\log n), and our new modifiedYehuda-Fogel algorithm. Our results show that the solutionscomputed by the greedy algorithm and the modified Yehuda-Fogelalgorithm are close to that computed by the approximationalgorithm even though the theoretical worst-case error bounds ofthese two algorithms are not proved to be within a constant timeof the optimal solution. Our study indicates that for practicaluse the greedy algorithm and the modified Yehuda-Fogel algorithmcan be good choices if the running time is a major concern.

/