Optimum quantizing of monotonic nondecreasing arrays

William W.Y. Hsu; Cheng Yu Lu; Ming-Yang Kao; Jan Ming Ho

doi:10.1109/CIFEr.2013.6611703

Optimum quantizing of monotonic nondecreasing arrays

William W.Y. Hsu, Cheng Yu Lu, Ming-Yang Kao, Jan Ming Ho

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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(kn²) 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	https://doi.org/10.1109/CIFEr.2013.6611703
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

Hsu, W. W. Y., Lu, C. Y., Kao, M-Y., & Ho, J. M. (2013). Optimum quantizing of monotonic nondecreasing arrays. In 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 (pp. 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). https://doi.org/10.1109/CIFEr.2013.6611703

Hsu, William W.Y. ; Lu, Cheng Yu ; Kao, Ming-Yang ; Ho, Jan Ming. / Optimum quantizing of monotonic nondecreasing arrays. 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. pp. 95-101 (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).

@inproceedings{d63a53e00f5245688db916295ded86f1,

title = "Optimum quantizing of monotonic nondecreasing arrays",

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{\"i}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.",

keywords = "Maximum Area, Monotonic Nondecreasing Convex Arrays, Quantization",

author = "Hsu, {William W.Y.} and Lu, {Cheng Yu} and Ming-Yang Kao and Ho, {Jan Ming}",

year = "2013",

month = oct

day = "28",

doi = "10.1109/CIFEr.2013.6611703",

language = "English (US)",

isbn = "9781467359214",

series = "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",

booktitle = "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",

note = "2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013 ; Conference date: 16-04-2013 Through 19-04-2013",

}

Hsu, WWY, Lu, CY, Kao, M-Y & Ho, JM 2013, Optimum quantizing of monotonic nondecreasing arrays. in 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., 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, pp. 95-101, 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013, Singapore, Singapore, 4/16/13. https://doi.org/10.1109/CIFEr.2013.6611703

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

T2 - 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013

Y2 - 16 April 2013 through 19 April 2013

ER -

Hsu WWY, Lu CY, Kao M-Y, Ho JM. Optimum quantizing of monotonic nondecreasing arrays. In 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). https://doi.org/10.1109/CIFEr.2013.6611703

Access to Document

10.1109/CIFEr.2013.6611703