Before revision:   Under the stability assumption, we present two sampling algorithms for computing approximate MEB with sample complexities independent of the number of input points ; further, we achieve the first sub-linear time single-criterion approximation algorithm for the MEB with outliers problem.
After revision:  Under the stability assumption, we present two sampling algorithms for computing approximate MEB with sample complexities independent of the number of input points n. In particular, the second algorithm has the sample complexity even independent of the dimensionality d. Further, we extend the idea to achieve a sub-linear time single-criterion approximation algorithm for the MEB with outliers problem.