Motivated by the arising realistic issues in big data, the problem of Minimum Enclosing Ball (MEB) with outliers has attracted a great deal of attention in recent years. Though several methods have been proposed in both theory and practice, most of them still suffer from the issues such as high time complexities or unstable performances for different datasets. For example, Kumar et al. \mbox{%DIFAUXCMD DBLP:journals/jea/KumarMY03 proposed the open problem " Are there practical methods for computing an MEB with outliers? " To answer this question, we  present a randomized algorithm for MEB with outliers in high dimension. In particular, we provide a more "robust" analysis for the core-set construction of MEB, and propose a couple of novel improvements to further reduce the time complexity. The ideas behind are interesting in their own right and we expect to apply them to solve more high-dimensional problems. We also extend our method to the problem of k-center clustering with outliers. To show the efficiency and practicality, we test our algorithms on random datasets and also apply it to solve outlier recognition on benchmark image datasets. To our best knowledge, this is the first result yielding both solid theoretical quality guarantee and promising practical performance for the problems .
Motivated by the arising realistic issues in big data, the problem of Minimum Enclosing Ball (MEB) with outliers has attracted a great deal of attention in recent years. Though several methods have been proposed in both theory and practice, most of them still suffer from the issues such as high time complexities or unstable performances for different datasets. For example, Kumar et al. proposed the open problem ` Are there practical methods for computing an MEB with outliers? ' To answer this question, we extend the idea of core-set and present a randomized algorithm for MEB with outliers in high dimension. In particular, we provide a more `robust' analysis for the core-set construction of MEB, and propose a couple of novel improvements to further reduce the time complexity. The ideas behind are interesting in their own right and we expect to apply them to solve more high-dimensional problems. To show the efficiency and practicality, we test our algorithm on random datasets and also apply it to handle outlier recognition on benchmark datasets. To our best knowledge, this is the first algorithm yielding both solid theoretical quality guarantee and promising practical performance for the problem of MEB with outliers .
D
\mbox{%DIFAUXCMD DBLP:journals/jea/KumarMY03
R
"
`
R
"
'
A
extend the idea of core-set and
R
"robust"
`robust'
D
We also extend our method to the problem of k-center clustering with outliers.
R
algorithms
algorithm
R
solve
handle
D
image
R
result
algorithm
R
problems
problem of MEB with outliers