Summary: The open covering property, also known in the literature as metric regularity, is investigated for certain classes of set-valued maps in a Banach space setting. The focus of the present study is on a perturbation approach for deriving open covering criteria, which stems from a theorem due to Milyutin, and which is developed here by means of an abstract notion of first-order approximation for single-valued maps between normed spaces. As a result, a criterion is achieved for parametric set-valued maps in terms of open covering of their strict approximation. Two applications are presented: the first one relates to Robinson-type theorems in the context of quasidifferential analysis, whereas the second concerns the estimation of the distance from the solution set to a nonsmooth problem in parametric convex optimization.