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

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