Chebyshev center of the intersection of balls: complexity, relaxation and approximation
From MaRDI portal
Publication:2020607
Abstract: 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.
Recommendations
- On Chebyshev center of the intersection of two ellipsoids
- Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
- The problem of a minimal ball enclosing k points
- On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
- Complexity and approximation of the smallest \(k\)-enclosing ball problem
Cites work
- scientific article; zbMATH DE number 1818892 (Why is no real title available?)
- scientific article; zbMATH DE number 3903874 (Why is no real title available?)
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- 10.1007/s11470-008-1002-x
- A Minimax Chebyshev Estimator for Bounded Error Estimation
- A new approximate algorithm for the Chebyshev center
- Convergence of the method of Chebyshev centers and some applications
- Convexity properties associated with nonconvex quadratic matrix functions and applications to quadratic programming
- Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation
- Improved semidefinite approximation bounds for nonconvex nonhomogeneous quadratic optimization with ellipsoid constraints
- Introductory lectures on convex optimization. A basic course.
- LMI approximations for the radius of the intersection of ellipsoids: Survey.
- Linear Matrix Inequalities in System and Control Theory
- Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
- On Chebyshev center of the intersection of two ellipsoids
- On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
- Optimal algorithms theory for robust estimation and prediction
- Polynomial Solvability of Variants of the Trust-Region Subproblem
- Regularization in Regression with Bounded Noise: A Chebyshev Center Approach
- Semidefinite Programming
- Strong Duality in Nonconvex Quadratic Optimization with Two Quadratic Constraints
- The minimum sphere covering a convex polyhedron
- Čebyšev sets in the space of convex bodies
Cited in
(8)- Cheaper relaxation and better approximation for multi-ball constrained quadratic optimization and extension
- On global solvability of a class of possibly nonconvex QCQP problems in Hilbert spaces
- On Chebyshev center of the intersection of two ellipsoids
- Chebyshev center and inscribed balls: properties and calculations
- An algorithm for finding the Chebyshev center of a convex polyhedron
- Covering a set by a convex compactum: error estimates and computation
- An algorithm for finding the generalized Chebyshev center of sets defined via their support functions
- On the convexity of a class of quadratic mappings and its application to the problem of finding the smallest ball enclosing a given intersection of balls
This page was built for publication: Chebyshev center of the intersection of balls: complexity, relaxation and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2020607)
