Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Fluctuated Fitting Under the \(\ell _1\)-metric
verfasst von : Kai Jin
Erschienen in: Frontiers in Algorithmics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.