# Chebyshev Center of the Intersection of Balls: Complexity, Relaxation and Approximation

arXiv: https://arxiv.org/abs/1901.07645 · HTML: https://mlsanity.com/paper/1901.07645/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jan 2019.

## Built on by (most cited first, 2 of 2)

- [Distributionally Robust Learning for Multi-source Unsupervised Domain Adaptation](https://mlsanity.com/paper/2309.02211/) (2023)
- [On a Gradient Approach to Chebyshev Center Problems with Applications to Function Learning](https://mlsanity.com/paper/2601.06434/) (2026)

## Abstract (arXiv)

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.