|
|||||
|
|
A branch-and-bound method for the minimum k?enclosing ball problem |
|
| Institution: | 1. Department of Management Science and Information Systems, Rutgers University, 100 Rockafeller Rd, Piscataway, 08854, NJ, USA;2. Martin Tuchman School of Management, NJIT, University Heights, 3000 Central Ave Building, Newark, 07102, NJ, USA |
| Abstract: | The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets. |
| Keywords: | Smallest covering ball Minimum enclosing ball 1-center with outliers Branch-and-bound |
| 本文献已被 ScienceDirect 等数据库收录！ | |