Chebyshev center of the intersection of balls: complexity, relaxation and approximation

Yong Xia, Mei-Jia Yang, Shu WangMath. Program 2021 · DOI

TL;DR

This paper tackles the problem of finding the smallest ball enclosing the intersection of several given balls. The authors prove this problem is NP-hard in general but solvable in polynomial time for specific cases. They introduce a new linear programming relaxation that leads to improved approximation bounds and a simpler derivation of existing solution methods.

What Problem Does This Paper Address?

The core problem is finding the "Chebyshev center" of the intersection of $p$ balls in $n$-dimensional space. Geometrically, this means finding the center of the smallest possible ball that completely contains the region formed by the overlap of all the given balls. This problem, known as the Chebyshev center problem (CCB), has applications in robust estimation and wireless network positioning. While simpler versions of the Chebyshev center problem are well-understood, finding the center for the intersection of balls is computationally challenging. Specifically, the inner maximization part of the problem involves a "uniform quadratic optimization" (UQ) problem, which can be NP-hard. The paper aims to understand the complexity of CCB, develop better approximation algorithms, and identify conditions under which it can be solved efficiently.

Methods

The paper introduces a novel linear programming (LP) relaxation for the inner maximization problem (UQ). This LP relaxation is shown to be equivalent to a semidefinite programming (SDP) relaxation under certain conditions. A key contribution is using this LP to provide a simpler derivation of the standard quadratic programming (SQP) relaxation for the original CCB problem. The authors also establish the first approximation bound for the SQP relaxation, which is independent of the number of balls ($p$). Furthermore, they analyze the conditions under which strong duality holds for the UQ problem and propose new sufficient conditions for this. Finally, the paper investigates cases where CCB is polynomially solvable, particularly when the dimension ($n$) or the difference between the number of balls and the dimension ($p-n$) is fixed.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • NP-Hardness of CCB: A significant finding is that the general Chebyshev center problem for the intersection of balls is NP-hard. This contrasts with the planar case ($n=2$), which is shown to be solvable in polynomial time.
  • LP Relaxation for UQ: The introduction of a new LP relaxation for the uniform quadratic optimization subproblem is a novel approach. This relaxation provides a tighter bound than previously known methods in certain scenarios and simplifies the derivation of existing SQP relaxations.
  • Improved Approximation Bounds: The paper provides the first approximation bound for the SQP relaxation of CCB, which is independent of the number of balls ($p$). This is a valuable theoretical result for understanding the quality of solutions obtained by this method.
  • Conditions for Strong Duality: New, more general conditions are identified for guaranteeing strong duality between the UQ problem and its SDP relaxation, extending previous results.
  • Fixed-Parameter Solvability: The paper demonstrates that CCB can be solved in polynomial time when either the dimension ($n$) or the difference ($p-n$) is fixed, offering practical computational advantages in such scenarios.

Key Results

  • The general Chebyshev center problem for the intersection of $p$ balls in $n$ dimensions is proven to be NP-hard.
  • The planar case ($n=2$) of the problem is strongly polynomially solvable in $O(p^2)$ time.
  • A new linear programming relaxation for the inner maximization problem (UQ) is proposed.
  • The first approximation bound for the SQP relaxation of CCB is established, showing that the returned solution is within a factor of $\frac{1-\gamma}{\sqrt{2}+\gamma}$ of the optimal value, where $\gamma$ depends on the ball parameters.
  • The problem is shown to be polynomially solvable when either $n$ or $p-n$ is fixed.

Limitations and Future Work

The paper notes that it is unknown whether the planar algorithm for CCB can be extended to solve the general case for $n \ge 3$. While the paper establishes conditions for polynomial solvability when $n$ or $p-n$ is fixed, it does not provide a general polynomial-time algorithm for all $n$ and $p$. The authors also leave open the question of whether CCB is strongly polynomially solvable even when $n=3$. Future work could focus on extending the planar algorithm to higher dimensions or exploring other approaches for the general case. Investigating tighter approximation bounds or exact polynomial-time algorithms for specific parameter regimes also remains an area for future research.

Summary updated

BibTeX
@article{xia2021chebyshev,
  author = {Yong Xia and Mei-Jia Yang and Shu Wang},
  title = {{Chebyshev center of the intersection of balls: complexity, relaxation and approximation}},
  journal = {Math. Program.},
  year = {2021},
  doi = {10.1007/s10107-020-01479-0},
}
Figure