Optimum quantizing of monotonic nondecreasing arrays

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

Research output: Chapter in Book/Report/Conference proceedingConference 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(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 languageEnglish (US)
Title of host publicationProceedings of the 2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
Pages95-101
Number of pages7
DOIs
StatePublished - Oct 28 2013
Event2013 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 2013Apr 19 2013

Publication series

NameProceedings 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

Other2013 IEEE Conference on Computational Intelligence for Financial Engineering and Economics, CIFEr 2013 - 2013 IEEE Symposium Series on Computational Intelligence, SSCI 2013
Country/TerritorySingapore
CitySingapore
Period4/16/134/19/13

Keywords

  • Maximum Area
  • Monotonic Nondecreasing Convex Arrays
  • Quantization

ASJC Scopus subject areas

  • Artificial Intelligence
  • Economics, Econometrics and Finance (miscellaneous)

Fingerprint

Dive into the research topics of 'Optimum quantizing of monotonic nondecreasing arrays'. Together they form a unique fingerprint.

Cite this