  


A branchandbound algorithm for the minimum radius kenclosing ball problem
Marta Cavaleiro(marta.cavaleirorutgers.edu) Abstract: The minimum $k$enclosing ball problem seeks the ball with smallest radius that contains at least $k$ of $m$ given points in a general $n$dimensional Euclidean space. This problem is NPhard. We present a branchandbound algorithm on the tree of the subsets of $k$ points to solve this problem. The nodes on the tree are ordered in a suitable way, which, complemented with a lastinfirstout search strategy, allows for only a small fraction of nodes to be explored. Additionally, an efficient dual algorithm to solve the subproblems at each node is employed. Keywords: minimum covering ball, smallest enclosing ball, 1center with outliers, branchandbound Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Combinatorial Optimization Citation: Download: [PDF] Entry Submitted: 07/11/2017 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  