A temporal constraint language \Gamma is a set of relations with first-order definitions in ({\mathbb{Q}}; <). Let CSP(\Gamma) denote the set of constraint satisfaction problem instances with relations from \Gamma. CSP(\Gamma) admits robust approximation if, for any \varepsilon \geq 0, given a (1-\varepsilon)-satisfiable instance of CSP(\Gamma), we can compute an assignment that satisfies at least a (1-f(\varepsilon))-fraction of constraints in polynomial time. Here, f(\varepsilon) is some function satisfying f(0)=0 and \lim\limits_{\varepsilon \to 0}f(\varepsilon)=0.

Firstly, we give a qualitative characterization of robust approximability: Assuming the Unique Games Conjecture, we give a necessary and sufficient condition on \Gamma under which CSP(\Gamma) admits robust approximation. Secondly, we give a quantitative characterization of robust approximability: Assuming the Unique Games Conjecture, we precisely characterize how f(\varepsilon) depends on \varepsilon for each \Gamma. We show that our robust approximation algorithms can be run in almost linear time.