科研之友
微信
新浪微博
Facebook
分享链接
摘要
We consider the online smoothing problem, in which a tracker is required to maintain distance no more than Delta a parts per thousand yen0 from a time-varying signal f while minimizing its own movement. The problem is determined by a metric space (X,d) with an associated cost function c:a"ea dagger'a"e. Given a signal f (1),f (2),aEuro broken vertical bar aX the tracker is responsible for producing a sequence a (1),a (2),aEuro broken vertical bar of elements of X that meet the proximity constraint: d(f (i) ,a (i) )a parts per thousand currency sign Delta. To complicate matters, the tracker is on-line-the value a (i) may only depend on f (1),aEuro broken vertical bar,f (i) -and wishes to minimize the cost of his travels, ac(d(a (i) ,a (i+1))). We evaluate such tracking algorithms competitively, comparing this with the cost achieved by an optimal adversary apprised of the entire signal in advance.
The problem was originally proposed by Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098-1107. ACM Press, New York, 2009), who considered the natural circumstance where the metric spaces are taken to be a"currency sign (k) with the a"" (2) metric and the cost function is equal to 1 unless the distance is zero (thus the tracker pays a fixed cost for any nonzero motion).
- We begin by studying arbitrary metric spaces with the "pay if you move" metric of Yi and Zhang (In: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms (SODA), pp. 1098-1107. ACM Press, New York, [2009]) described above and describe a natural randomized algorithm that achieves a O(logb (Delta))-competitive ratio, where b (Delta)=max (xaX) |B (Delta)(x)| is the maximum number of points appearing in any ball of radius Delta. We show that this bound is tight.
We then focus on the metric space a"currency sign with natural families of monotone cost functions c(x)=x (p) for some pa parts per thousand yen0. We consider both the expansive case (pa parts per thousand yen1) and the contractive case (p < 1), and show that the natural lazy algorithm performs well in the expansive case. In the contractive case, we introduce and analyze a novel deterministic algorithm that achieves a constant competitive ratio depending only on p. Finally, we observe that by slightly relaxing the guarantee provided by the tracker, one can obtain natural analogues of these algorithms that work in continuous metric spaces.
- 出版日期2014-1
