The Minimum Covering l pb -Hypersphere Problem

The minimu vering hypersphere problem is defined as to find a hypersphere of minimum radius enclosing a finite set of given points in ⁿ. A hypersphere is a set S(c,r)={x ⁿ : 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)=l₂(x-c). We consider the extension of this problem when d(x, c) is given by any l_pb-norm, where 1<p and b=(b₁,...,b_n) with b_j>0, j=1,...,n, then S(c,r) is called an l_pb-hypersphere, in particular for p=2 and b_j=1, j=1,..., n, we obtain the l₂-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 l_pb-hypersphere enclosing a large set of points in ⁿ.