A branch-and-bound method for the minimum k−enclosing ball problem

Marta Cavaleiro, Farid Alizadeh

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish (US)
Pages (from-to)274-280
Number of pages7
JournalOperations Research Letters
Volume50
Issue number3
DOIs
StatePublished - May 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • 1-center with outliers
  • Branch-and-bound
  • Minimum enclosing ball
  • Smallest covering ball

Fingerprint

Dive into the research topics of 'A branch-and-bound method for the minimum k−enclosing ball problem'. Together they form a unique fingerprint.

Cite this