Abstract
This paper presents an efficient algorithm for finding the optimal k-cuts of a nondecreasing array of size n that produces the maximum area under the points. The naïve approach uses a dynamic programming algorithm which requires O(kn2) time, where n is the size of the array. This algorithm is time consuming for large n or k and thus inappropriate. We design faster algorithms by discovering and proving some nice properties of the nondecreasing arrays, finding convex hull, and by continuous-to-discrete transformation. We believe that an O(kn) time algorithm exists and show a heuristic algorithm.
| Original language | English (US) |
|---|---|
| Title of host publication | Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 |
| Pages | 95-101 |
| Number of pages | 7 |
| DOIs | |
| State | Published - Oct 28 2013 |
| Event | 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 - Singapore, Singapore Duration: Apr 16 2013 → Apr 19 2013 |
Publication series
| Name | Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 |
|---|
Other
| Other | 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 |
|---|---|
| Country | Singapore |
| City | Singapore |
| Period | 4/16/13 → 4/19/13 |
Fingerprint
Keywords
- Maximum Area
- Monotonic Nondecreasing Convex Arrays
- Quantization
ASJC Scopus subject areas
- Artificial Intelligence
- Economics, Econometrics and Finance (miscellaneous)
Cite this
}
Optimum quantizing of monotonic nondecreasing arrays. / Hsu, William W.Y.; Lu, Cheng Yu; Kao, Ming-Yang; Ho, Jan Ming.
Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013. 2013. p. 95-101 6611703 (Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Optimum quantizing of monotonic nondecreasing arrays
AU - Hsu, William W.Y.
AU - Lu, Cheng Yu
AU - Kao, Ming-Yang
AU - Ho, Jan Ming
PY - 2013/10/28
Y1 - 2013/10/28
N2 - This paper presents an efficient algorithm for finding the optimal k-cuts of a nondecreasing array of size n that produces the maximum area under the points. The naïve approach uses a dynamic programming algorithm which requires O(kn2) time, where n is the size of the array. This algorithm is time consuming for large n or k and thus inappropriate. We design faster algorithms by discovering and proving some nice properties of the nondecreasing arrays, finding convex hull, and by continuous-to-discrete transformation. We believe that an O(kn) time algorithm exists and show a heuristic algorithm.
AB - This paper presents an efficient algorithm for finding the optimal k-cuts of a nondecreasing array of size n that produces the maximum area under the points. The naïve approach uses a dynamic programming algorithm which requires O(kn2) time, where n is the size of the array. This algorithm is time consuming for large n or k and thus inappropriate. We design faster algorithms by discovering and proving some nice properties of the nondecreasing arrays, finding convex hull, and by continuous-to-discrete transformation. We believe that an O(kn) time algorithm exists and show a heuristic algorithm.
KW - Maximum Area
KW - Monotonic Nondecreasing Convex Arrays
KW - Quantization
UR - http://www.scopus.com/inward/record.url?scp=84886075767&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84886075767&partnerID=8YFLogxK
U2 - 10.1109/CIFEr.2013.6611703
DO - 10.1109/CIFEr.2013.6611703
M3 - Conference contribution
AN - SCOPUS:84886075767
SN - 9781467359214
T3 - Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
SP - 95
EP - 101
BT - Proceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
ER -