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.