  We study the n-dimensional problem of finding the smallest ball enclosing the
intersection of p given balls, the so-called Chebyshev center problem (CCB). It
is a minimax optimization problem and the inner maximization is a uniform
quadratic optimization problem (UQ). When p<=n, (UQ) is known to enjoy a strong
duality and consequently (CCB) is solved via a standard convex quadratic
programming (SQP). In this paper, we first prove that (CCB) is NP-hard and the
special case when n = 2 is strongly polynomially solved. With the help of a
newly introduced linear programming relaxation (LP), the (SQP) relaxation is
reobtained more directly and the first approximation bound for the solution
obtained by (SQP) is established for the hard case p>n. Finally, also based on
(LP), we show that (CCB) is polynomially solved when either n or p-n(> 0) is
fixed.
