An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation
<|reference_start|>An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation: Monotonicity is a simple yet significant qualitative characteristic. We consider the problem of segmenting an array in up to K segments. We want segments to be as monotonic as possible and to alternate signs. We propose a quality metric for this problem, present an optimal linear time algorithm based on novel formalism, and compare experimentally its performance to a linear time top-down regression algorithm. We show that our algorithm is faster and more accurate. Applications include pattern recognition and qualitative modeling.<|reference_end|>
@article{lemire2007an,
    title={An Optimal Linear Time Algorithm for Quasi-Monotonic Segmentation},
    author={Daniel Lemire, Martin Brooks, Yuhong Yan},
    journal={arXiv preprint arXiv:cs/0702142},
    year={2007},
    archivePrefix={arXiv},
    eprint={cs/0702142},
    primaryClass={cs.DS cs.DB}
}