Marta Cavaleiro

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

  • Farid Alizadeh
  • Marta Cavaleiro
    • Categories (Mixed) Integer Nonlinear Programming, Combinatorial Optimization Tags , , ,

    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 … Read more

    A faster dual algorithm for the Euclidean minimum covering ball problem

  • Farid Alizadeh
  • Marta Cavaleiro
    • Categories Convex Optimization Tags , , , ,

    Dearing and Zeck presented a dual algorithm for the problem of the minimum covering ball in $\mathbb{R}^n$. Each iteration of their algorithm has a computational complexity of at least $\mathcal O(n^3)$. In this paper we propose a modification to their algorithm that, together with an implementation that uses updates to the QR factorization of a … Read more