Motivated by range counting problems, relative approximations have become a central tool in computational geometry. In fact, they were introduced by Har-Peled and Sharir, who derived them from the seminal work of Li, Long, and Srinivasan in the theory of machine learning. In this talk I will discuss properties of relative approximations, and present improved upper bounds for their size under certain favorable assumptions. Our approach is probabilistic, where we apply the constructive version of the Asymmetric Lovasz Local Lemma.