Computational Optimization & Applications. 9(1):85–97, JANUARY 1998

Issn Print: 0926-6003

Publication Date: January 1998

# The Minimum Covering lpb-Hypersphere Problem

B. PelegrÍN;L. CáNovas;

+ Author Information

Dpto. Estadistica e Investigation Operativa. Universidad de Murcia. Campus de Espinardo. 30071-Murcia (Spain)

### Abstract

The minimu vering hypersphere problem is defined as to find a hypersphere of minimum radius enclosing a finite set of given points in IRn. A hypersphere is a set S(c,r))={x∈ IRn: d(x,c)) ≤ r}, where c is the center of S, r is the radius of S and d(x,c)) is the Euclidean distance between x and c, i.e., d(x,c))=l2(x-c)). We consider the extension of this problem when d(x,c)) is given by any lpb-norm, where 1<p < ∞ and b=(b1,…,bn)) with bj> 0,j = 1,…,n, then S(c,r))is called an lpb-hypersphere, in particular for p=2 and bj=1, j=1,…,n, we obtain the l2-norm. We study some properties and propose some primal and dual algorithms for the extended problem, which are based on the feasible directions method and on the Wolfe duality theory. By computational experiments, we compare the proposed algorithms and show that they can be used to approximate the smallest lpb-hypersphere enclosing a large set of points in IRn.