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

Marta Cavaleiro; Farid Alizadeh

doi:10.1016/j.orl.2022.02.007

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

Marta Cavaleiro, Farid Alizadeh

Mgmt Science & Info Systems

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	274-280
Number of pages	7
Journal	Operations Research Letters
Volume	50
Issue number	3
DOIs	https://doi.org/10.1016/j.orl.2022.02.007
State	Published - 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

Access to Document

10.1016/j.orl.2022.02.007

Cite this

@article{4eea3fa44aac45f4bd10089a2d73038f,

title = "A branch-and-bound method for the minimum k−enclosing ball problem",

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 = "1-center with outliers, Branch-and-bound, Minimum enclosing ball, Smallest covering ball",

author = "Marta Cavaleiro and Farid Alizadeh",

note = "Publisher Copyright: {\textcopyright} 2022 Elsevier B.V.",

year = "2022",

month = may,

doi = "10.1016/j.orl.2022.02.007",

language = "English (US)",

volume = "50",

pages = "274--280",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

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

AU - Cavaleiro, Marta

AU - Alizadeh, Farid

PY - 2022/5

Y1 - 2022/5

N2 - 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.

AB - 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.

KW - 1-center with outliers

KW - Branch-and-bound

KW - Minimum enclosing ball

KW - Smallest covering ball

UR - http://www.scopus.com/inward/record.url?scp=85125749415&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85125749415&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2022.02.007

DO - 10.1016/j.orl.2022.02.007

M3 - Article

AN - SCOPUS:85125749415

VL - 50

SP - 274

EP - 280

JO - Operations Research Letters

JF - Operations Research Letters

SN - 0167-6377

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this