Design and Performance Evaluation of Sequence Partition Algorithms |
| |
Authors: | Bing Yang Jing Chen En-Yue Lu Si-Qing Zheng |
| |
Affiliation: | (1) Cisco Systems, 2200 East President George Bush Highway, Richardson, TX, 75082, U.S.A.;(2) Telecom. Engineering Program, University of Texas at Dallas, Richardson, TX, 75083, U.S.A.;(3) Department of Mathematics and Computer Science, Salisbury University, Salisbury, MD, 21801, U.S.A.;(4) Department of Computer Science, University of Texas at Dallas, Richardson, TX, 75083, U.S.A. |
| |
Abstract: | 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. |
| |
Keywords: | monotone subsequence permutation algorithm NP-complete approximation complexity |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载全文 |
|