### 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^{2}) 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

*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

}

*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.

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 -