Advertisement
Published in:
2017 | OriginalPaper | Chapter
Fluctuated Fitting Under the \(\ell _1\)-metric
Author : Kai Jin
Published in: Frontiers in Algorithmics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We consider the problem of fitting a given sequence of integers by an \((\alpha ,\beta )\)-fluctuated one. For a sequence of numbers, those elements which are larger than their direct precursors are called ascends, those elements which are smaller than their direct precursors are called descends. A sequence is said to be \((\alpha ,\beta )\)-fluctuated if there is a descend between any \(\alpha +1\) ascends and an ascend between any \(\beta +1\) descends; or equivalently, if it has at most \(\alpha \) consecutive ascends and at most \(\beta \) consecutive descends, when adjacent equal values are ignored.
Given a sequence of integers \(\mathbf {a}=(a_1,\ldots ,a_n)\) and two parameters \(\alpha ,\beta \) in [1, n], we compute (1) a sequence \(\mathbf {b}=(b_1,\ldots ,b_n)\) of integers that is \((\alpha ,\beta )\)-fluctuated and is closest to \(\mathbf {a}\) among all such sequences; (2) a sequence \(\mathbf {b}'=(b'_1,\ldots ,b'_n)\) of integers that is \((\alpha ,\beta )\)-fluctuated and is bounded by \(\mathbf {a}\) (i.e. \(b'_i\le a_i\) for all i) and is closest to \(\mathbf {a}\) among all such sequences. We measure the distance between sequences under \(\ell _1\) metric.
Our algorithm runs in \(O((\alpha +\beta )\cdot n)\) time, which is linear when \(\alpha ,\beta \) are considered as constants. We also show that a variation of our problem can be solved in the same time complexity. We achieve our result mainly by exploiting and utilizing the property of the closest sequence.