Online gamma-Covering in the Relaxed Sliding Window Model - 
In this work, we propose the relaxed sliding window model. Sliding windows is an online algorithmic model where algorithms must maintain an approximate solution on the last W datapoints as they arrive in an online fashion, hence the W-sized "window". In relaxed sliding windows, algorithms are allowed to compare their solution on the last W datapoints to the best solution on the last 2W datapoints. This relaxation admits much simpler and more natural algorithms as well as giving the opportunity for stronger approximation guarantees. We illustrate this, for one, through the gamma-covering problem, where we strive to identify a minimum-sized set of covering points such that the input data is always within a gamma distance of some covering point. Specifically, we present a simple relaxed sliding window 2-approximate algorithm for 2gamma-covering and contrast it with the much more complicated sliding window optimal 6gamma-covering.