Optimization Online


A branch-and-bound algorithm for the minimum radius k-enclosing ball problem

Marta Cavaleiro(marta.cavaleiro***at***rutgers.edu)
Farid Alizadeh(farid.alizadeh***at***rutgers.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 NP-hard. We present a branch-and-bound 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 last-in-first-out 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, 1-center with outliers, branch-and-bound

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization


Download: [PDF]

Entry Submitted: 07/11/2017
Entry Accepted: 07/11/2017
Entry Last Modified: 07/11/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society