Design and Performance Evaluation of Sequence Partition Algorithms

Abstract
Tradeoffs between timecomplexities and solution optimalities are important when selectingalgorithms for an NPhard problem in different applications. Also,the distinction between theoretical upper bound and actual solutionoptimality for realistic instances of an NPhard 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 isNPhard 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 theYehudaFogel 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 modifiedYehudaFogel algorithm. Our results show that the solutionscomputed by the greedy algorithm and the modified YehudaFogelalgorithm are close to that computed by the approximationalgorithm even though the theoretical worstcase 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 YehudaFogel algorithmcan be good choices if the running time is a major concern.

