کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
434341 | 689719 | 2014 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Closest periodic vectors in LpLp spaces Closest periodic vectors in LpLp spaces](/preview/png/434341.png)
The problem of finding the period of a vector V is central to many applications. Let V′V′ be a periodic vector closest to V under some metric. We seek this V′V′, or more precisely we seek the smallest period that generates V′V′. In this paper we consider the problem of finding the closest periodic vector in LpLp spaces. The measures of “closeness” that we consider are the metrics in the different LpLp spaces. Specifically, we consider the L1,L2L1,L2 and L∞L∞ metrics. In particular, for a given n-dimensional vector V , we develop O(n2)O(n2) time algorithms (a different algorithm for each metric) that construct the smallest period that defines such a periodic n -dimensional vector V′V′. We call that vector the closest periodic vector of V under the appropriate metric. We also show (three) O˜(n) time constant approximation algorithms for the period of the approximate closest periodic vector.
Journal: Theoretical Computer Science - Volume 533, 8 May 2014, Pages 26–36