Given a set of numerical values and a threshold, finding the minimum subset from the set such that its sum is not less than the threshold value, is termed as selectsum problem which is widely applicable in data compre...
详细信息
Given a set of numerical values and a threshold, finding the minimum subset from the set such that its sum is not less than the threshold value, is termed as selectsum problem which is widely applicable in data compression and image processing. In this article, we provide two new linear-time algorithms for the problem. Different from the current approaches that directly calling the Selection algorithms for partitioning on median elements, our proposed algorithms embed the Selection process and use cheap pivot elements for partitioning. The experimental tests indicate these two new algorithms are significant faster than the current existing algorithms on larger data sets.
暂无评论