For a large class of robustness problems with uncertain parameter vector q confined to a box Q, there are many papers providing results along the following lines. The desired performance specification is robustly satisfied for all q epsilon Q if and only if it is satisfied at each vertex q(2) of Q. Since the number of vertices of Q explodes combinatorically with the dimension of q, the computation associated with the implementation of such results is often intractable. The main point of this note is to introduce a new approach to such problems aimed at alleviation of this computational complexity problem. To this end, the notion of approximate feasibility is introduced, and the theory which follows from this definition is vertex-free.