Multi-dimensional online tracking

We propose and study a new class of online problems, which we call online tracking. Suppose an observer, say Alice, observes a multi-valued function f : ℤ⁺ → ℤ^d over time in an online fashion, i.e., she only sees f(t) for t ≤ t_now where t_now is the current time. She would like to keep a tracker, say Bob, informed of the current value of f at all times. Under this setting, Alice could send new values of f to Bob from time to time, so that the current value of f is always within a distance of Δ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire f in advance. We also consider variations of the problem where Alice is allowed to send "predictions" to Bob, to further reduce communication for well-behaved functions. These online tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems. Copyright © by SIAM