Before revision:  We also show that our idea can be extended to  the general case of MEB with outliers ({\em i.e.,} without the stability assumption) , and obtain a sub-linear time bi-criteria approximation algorithm. Our results can be viewed as a new step along the direction of beyond worst-case analysis .
After revision:  We also show that our idea can be extended to the general case of MEB with outliers ({\em i.e.,} without the stability assumption) , and obtain a sub-linear time bi-criteria approximation algorithms for these problems respectively; the algorithms have sample sizes independent of the number of points n and the dimensionality d, which significantly improve the time complexities of existing algorithms. We expect that our technique will be applicable to design sub-linear time algorithms for other shape fitting with outliers problems .