Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
393020 | Information Sciences | 2013 | 7 Pages |
Abstract
Motivated by the wavelet compression techniques and their applications, we consider the following problem: Given an unsorted array of numerical values and a threshold, what is the minimum number of elements chosen from the array, such that the sum of these elements is not less than the threshold value. In this article, we first provide two linear time algorithms for the problem. We then demonstrate the efficacy of these algorithms through experiments. Lastly, as an application of this research, we indicate that the construction of wavelet synopses on a prescribed error bound (in L2 metric) can be solved in linear time.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Yan Jiang, Chaoyi Pang, Hao Lan Zhang, Junhu Wang, Tongliang Li, Qing Zhang, Jing He,